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.

DateSpeakerTitle
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
(Colloquium)
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
(Colloquium)
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
• Talks will generally be held on Fridays from 10:45-11:45 a.m. in 219 Hammond Building (unless they are part of the departmental colloquium, in which case they will be held from 2-3 p.m. in 113 IST Building (Cybertorium)). Any unusual date/time/location is highlighted in the schedule.
• If you would like to speak, please email us at: theory [at] cse [dot] psu [dot] edu.
• If you want to receive announcements of upcoming talks, please join the theory mailing list.
Archives

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