The 4/3 Additive Spanner Exponent is Tight

Thursday, December 10, 2015 - 4:00pm to 5:00pm
3:45 pm
Amir Abboud
Stanford University
A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original graph. It is well known that there is a smooth tradeoff between the sparsity of a spanner and the quality of its approximation, so long as distance error is measured multiplicatively. A central open question in the field is to prove or disprove whether such a tradeoff exists also in the regime of additive error.  That is, is it true that for all e>0, there is a constant k such that every graph has a spanner on O(n^{1+e}) edges that preserves its pairwise distances up to +k?
Previous lower bounds are consistent with a positive resolution to this question, while previous upper bounds exhibit the beginning of a tradeoff curve: all graphs have +2 spanners on O(n^3/2) edges, +4 spanners on ~O(n^7/5) edges, and +6 spanners on O(n^4/3) edges. However, progress has mysteriously halted at the n^4/3 bound, and despite significant effort from the community, the question has remained open for all 0 < e < 1/3.
Our main result is a surprising negative resolution of the open question, even in a highly generalized setting.  We show a new information theoretic incompressibility bound: there is no function that compresses graphs into O(n^{4/3 - e}) bits so that distance information can be recovered within +n^o(1) error. As a special case of our theorem, we get a tight lower bound on the sparsity of additive spanners: the +6 spanner on O(n^4/3) edges cannot be improved in the exponent, even if any subpolynomial amount of additive error is allowed.  
In this talk, I will describe our construction of these incompressible graphs. 
This is a joint work with Greg Bodwin.