2026-07-20T14:47:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20171 2024-07-02T07:52:49Z ddc:004 open_access

Additive Spanner Lower Bounds with Optimal Inner Graph Structure Bodwin, Greg Hoppenworth, Gary Vassilevska Williams, Virginia Wein, Nicole Xu, Zixuan Additive Spanners Graph Theory We construct n-node graphs on which any O(n)-size spanner has additive error at least +Ω(n^{3/17}), improving on the previous best lower bound of Ω(n^{1/7}) [Bodwin-Hoppenworth FOCS '22]. Our construction completes the first two steps of a particular three-step research program, introduced in prior work and overviewed here, aimed at producing tight bounds for the problem by aligning aspects of the upper and lower bound constructions. More specifically, we develop techniques that enable the use of inner graphs in the lower bound framework whose technical properties are provably tight with the corresponding assumptions made in the upper bounds. As an additional application of our techniques, we improve the corresponding lower bound for O(n)-size additive emulators to +Ω(n^{1/14}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Greg Bodwin and Gary Hoppenworth and Virginia Vassilevska Williams and Nicole Wein and Zixuan Xu 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.28 urn:nbn:de:0030-drops-201715 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.28 eng https://creativecommons.org/licenses/by/4.0/legalcode