Additive Spanner Lower Bounds with Optimal Inner Graph Structure
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916227688955904 |
|---|---|
| author | Bodwin, Greg Hoppenworth, Gary Williams, Virginia Vassilevska Wein, Nicole Xu, Zixuan |
| author_facet | Bodwin, Greg Hoppenworth, Gary Williams, Virginia Vassilevska Wein, Nicole Xu, Zixuan |
| contents | 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})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_18337 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Additive Spanner Lower Bounds with Optimal Inner Graph Structure Bodwin, Greg Hoppenworth, Gary Williams, Virginia Vassilevska Wein, Nicole Xu, Zixuan Data Structures and Algorithms 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})$. |
| title | Additive Spanner Lower Bounds with Optimal Inner Graph Structure |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.18337 |