Theoretical Computer Science Group

Theory Seminar Schedule for Fall 2016

The weekly Theory seminar provides an opportunity to get exposed to cutting edge research in theoretical computer science, to learn to understand technical material from talks and to give technical presentations. Graduate students interested in doing research in algorithms, complexity theory, cryptography, quantum computing and related areas are strongly encouraged to attend.

August 26
10:45 am
Organizational Meeting (Location: 357, IST Building (Theory Lab))
September 2 TBD TBD
September 9 Greg Bodwin (Stanford) The 4/3 Additive Spanner Exponent is Tight
September 16 Nai-Hui Chia (PSU) TBD
September 23
Jan Holub (CVUT) TBD
September 30 Nima Haghpanah (PSU, Economics) TBD
October 7 Ramesh Krishnan (PSU) TBD
October 14 Meiram Murzabulatov (PSU) TBD
October 21 Adam Smith (PSU) Privacy, Information and Generalization in Adaptive Data Analysis
October 28
Shafi Goldwasser (MIT) TBD (Kelly Distinguished lecture)
November 4 Nithin Varma (PSU) TBD
November 11 Jiayu Yang (PSU) TBD
November 18 Om Thakkar (PSU) TBD
November 25 Thanksgiving week, no seminar
December 2 Ishan Behoora (PSU) TBD
December 9 TBD TBD

Spring 2007     Fall 2007     Spring 2008     Summer 2008     Fall 2008     Spring 2009     Fall 2009     Spring 2010     Fall 2010     Spring 2011     Fall 2011     Spring 2012     Fall 2012     Spring 2013     Fall 2013     Fall 2014     Spring 2015     Fall 2015    Spring 2016

The 4/3 Additive Spanner Exponent is Tight

A $+k$ additive spanner is a sparse subgraph that preserves all pairwise distances up to additive error $+k$. A classic result in this field states that all graphs have +6 spanners on $n^{4/3}$ edges, but no sparser spanners are known for any constant $k$. Meanwhile, current lower bound allow for the possibility of constant-error additive spanners on $n^{1 + \epsilon}$ edges for any $\epsilon > 0$. It is considered a central open problem to prove the existence/nonexistence of these nearly-linear sized additive spanners.
We resolve this question in the negative by constructing a family of graphs that provably have no $+n^{o(1)}$ additive spanners on $n^{4/3 - \epsilon}$ edges. In this talk, we will describe the construction technique. We will then discuss some extensions and implications of this new lower bound.
Joint work with Amir Abboud