Date: Friday, January 22, 2016
Location: 3725 BBB (10:00 AM to 11:00 AM)
Title: The 4/3 Additive Spanner Exponent is Tight
Abstract: This is a presentation of recent work by Amir Abboud and Greg Bodwin.
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 ke such that every graph has a spanner on O(n^{1+eps}) edges that preserves its pairwise distances up to +c(eps). 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 n4/3 bound, and despite significant effort from the community, the question has remained open for all 0
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 mathematical function that compresses graphs into O(n^{4/3eps}) bits so that distance information can be recovered within +n^{o(1)} error.
Manuscript available at arXiv:1511.00700.
Files:
Speaker: Seth Pettie
Institution: UM
Event Organizer: schoeneb
