{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:22Z","timestamp":1787323522096,"version":"build-2736575974"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1514383"],"award-info":[{"award-number":["CCF-1514383"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1637546"],"award-info":[{"award-number":["CCF-1637546"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1815316"],"award-info":[{"award-number":["CCF-1815316"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We prove better lower bounds on additive spanners and emulators, which are lossy compression schemes for undirected graphs, as well as lower bounds on shortcut sets, which reduce the diameter of directed graphs. We prove that any $O(n)$-size shortcut set cannot bring the diameter below $\\Omega(n^{1\/6})$ and that any $O(m)$-size shortcut set cannot bring it below $\\Omega(n^{1\/11})$. These improve Hesse's [ Proceedings of the 14 th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, MD, 2003] lower bound of $\\Omega(n^{1\/17})$. By combining these constructions with Abboud and Bodwin's [ J. ACM, 64 (2017), 28] edge-splitting technique, we get additive stretch lower bounds of $+\\Omega(n^{1\/11})$ for $O(n)$-size spanners and $+\\Omega(n^{1\/18})$ for $O(n)$-size emulators. These improve Abboud and Bodwin's $+\\Omega(n^{1\/22})$ lower bounds for both spanners and emulators.<\/jats:p>","DOI":"10.1137\/19m1306154","type":"journal-article","created":{"date-parts":[[2021,9,20]],"date-time":"2021-09-20T12:00:46Z","timestamp":1632139246000},"page":"2129-2144","source":"Crossref","is-referenced-by-count":7,"title":["Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts"],"prefix":"10.1137","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9799-0981","authenticated-orcid":true,"given":"Shang-En","family":"Huang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,9,20]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/3088511"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1105815"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303421"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10056"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s002080050217"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868242"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.32.12.331"},{"key":"atypb8","first-page":"600","author":"Bodwin G.","year":"2017","journal-title":"Spain"},{"key":"atypb9","unstructured":"G. Bodwin,\n                      A Note on Distance-Preserving Graph Sparsification\n                      , preprint, arXiv:2001.07741, 2020,https:\/\/arxiv.org\/abs\/2001.07741."},{"key":"atypb10","first-page":"377","author":"Bodwin G.","year":"2015","journal-title":"Israel"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"G. Bodwin and V. V. Williams,\n                      Better distance preservers and additive spanners\n                      , in Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington, VA, 2016.","DOI":"10.1137\/1.9781611974331.ch61"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"N. Cao, J. T. Fineman, and K. Russell,\n                      Efficient construction of directed hopsets and parallel approximate shortest paths\n                      , in Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, Chicago, IL, 2020.","DOI":"10.1145\/3357713.3384270"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"S. Chechik,\n                      New additive spanners\n                      , in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013, New Orleans, LA, pp. 498-512.","DOI":"10.1137\/1.9781611973105.36"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/050630696"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327908"},{"key":"atypb16","first-page":"1","volume":"130","author":"Elkin M.","year":"2020","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701393384"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"J. T. Fineman,\n                      Nearly work-efficient parallel algorithm for digraph reachability\n                      , in STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, Los Angeles, CA, June 25-29, 2018, pp. 457-470.","DOI":"10.1145\/3188745.3188926"},{"key":"atypb19","unstructured":"W. Hesse,\n                      Directed graphs requiring large numbers of shortcuts\n                      , in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, MD, 2003."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2018.10.001"},{"key":"atypb21","first-page":"277","author":"Knudsen M. B. T.","year":"2014","journal-title":"Denmark"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"Y. P. Liu, A. Jambulapati, and A. Sidford,\n                      Parallel reachability in almost linear work and square root depth\n                      , in Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), Baltimore, MD, 2019.","DOI":"10.1109\/FOCS.2019.00098"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644022"},{"key":"atypb24","first-page":"205","author":"Thorup M.","year":"1992","journal-title":"Springer"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001668"},{"key":"atypb26","first-page":"802","author":"Thorup M.","year":"2006","journal-title":"Miami, FL"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"D. P. Woodruff,\n                      Lower bounds for additive spanners, emulators, and more\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Berkeley, CA, 2006, pp. 389-398.","DOI":"10.1109\/FOCS.2006.45"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1306154","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:07:21Z","timestamp":1787321241000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1306154"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1306154"],"URL":"https:\/\/doi.org\/10.1137\/19m1306154","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}