{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T09:22:07Z","timestamp":1778664127126,"version":"3.51.4"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,8,31]],"date-time":"2017-08-31T00:00:00Z","timestamp":1504137600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"BSF","award":["BSF:2012338"],"award-info":[{"award-number":["BSF:2012338"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1417238, CCF-1528078 and CCF-1514339"],"award-info":[{"award-number":["CCF-1417238, CCF-1528078 and CCF-1514339"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,8,31]]},"abstract":"<jats:p>\n            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\n            <jats:italic>multiplicatively<\/jats:italic>\n            . A central open question in the field is to prove or disprove whether such a tradeoff exists also in the regime of\n            <jats:italic>additive<\/jats:italic>\n            error. That is, is it true that for all \u03b5 &gt; 0, there is a constant\n            <jats:italic>k<\/jats:italic>\n            <jats:sub>\u03b5<\/jats:sub>\n            such that every graph has a spanner on\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1+\u03b5<\/jats:sup>\n            ) edges that preserves its pairwise distances up to +\n            <jats:italic>\n              k\n              <jats:sub>\u03b5<\/jats:sub>\n            <\/jats:italic>\n            ? 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\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            ) edges, +4 spanners on\n            <jats:italic>\u00d5<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>7\/5<\/jats:sup>\n            ) edges, and +6 spanners on\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/3<\/jats:sup>\n            ) edges. However, progress has mysteriously halted at the\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/3<\/jats:sup>\n            bound, and despite significant effort from the community, the question has remained open for all 0 &lt; \u03b5 &lt; 1\/3.\n          <\/jats:p>\n          <jats:p>\n            Our main result is a surprising negative resolution of the open question, even in a highly generalized setting. We show a new information theoretic\n            <jats:italic>incompressibility<\/jats:italic>\n            bound: There is no function that compresses graphs into\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/3 \u2212 \u03b5<\/jats:sup>\n            ) bits so distance information can be recovered within +\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>o(1)<\/jats:sup>\n            error. As a special case of our theorem, we get a\n            <jats:italic>tight<\/jats:italic>\n            lower bound on the sparsity of additive spanners: the +6 spanner on\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/3<\/jats:sup>\n            ) edges cannot be improved in the exponent, even if any\n            <jats:italic>subpolynomial<\/jats:italic>\n            amount of additive error is allowed. Our theorem implies new lower bounds for related objects as well; for example, the 20-year-old +4 emulator on\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/3<\/jats:sup>\n            ) edges also cannot be improved in the exponent unless the error allowance is polynomial.\n          <\/jats:p>\n          <jats:p>\n            Central to our construction is a new type of graph product, which we call the\n            <jats:italic>Obstacle Product<\/jats:italic>\n            . Intuitively, it takes two graphs\n            <jats:italic>G<\/jats:italic>\n            ,\n            <jats:italic>H<\/jats:italic>\n            and produces a new graph\n            <jats:italic>G<\/jats:italic>\n            \u2297\n            <jats:italic>H<\/jats:italic>\n            whose shortest paths structure looks locally like\n            <jats:italic>H<\/jats:italic>\n            but globally like\n            <jats:italic>G<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3088511","type":"journal-article","created":{"date-parts":[[2017,9,8]],"date-time":"2017-09-08T13:13:38Z","timestamp":1504876418000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["The 4\/3 Additive Spanner Exponent Is Tight"],"prefix":"10.1145","volume":"64","author":[{"given":"Amir","family":"Abboud","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA"}]},{"given":"Greg","family":"Bodwin","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA"}]}],"member":"320","published-online":{"date-parts":[[2017,9,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884495"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039722"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303421"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201996)","author":"Aingworth Donald","year":"1996"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875540"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2805875.2805976"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Baswana Surender","year":"2005"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868242"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.32.12.331"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039725"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688103"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884496"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903)","author":"Bollob\u00e1s B\u00e9la","year":"2003"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627853"},{"key":"e_1_2_1_17_1","volume-title":"Encyclopedia of Algorithms","author":"Chechik Shiri"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9478-x"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.05.017"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/050630696"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 30th Symposium on Theoretical Aspects of Computer Science (STACS\u201913)","author":"Cygan Marek","year":"2013"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875495"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.06.007"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.03.036"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.10.002"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103968"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701393384"},{"key":"e_1_2_1_28_1","unstructured":"Paul Erd\u00f6s. 1964. Extremal problems in graph theory. Theory of Graphs and Its Applications (1964) 29--36.  Paul Erd\u00f6s. 1964. Extremal problems in graph theory. Theory of Graphs and Its Applications (1964) 29--36."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 32nd Symposium on Theoretical Aspects of Computer Science (STACS\u201915)","author":"Kavitha Telikepalli","year":"2015"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_51"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08404-6_24"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626491000197"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230230417"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02761110"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43951-7_49"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644022"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_22"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109645"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.45"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880918.1880970"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3088511","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3088511","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3088511","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:07Z","timestamp":1750217407000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3088511"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,31]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/3088511"],"URL":"https:\/\/doi.org\/10.1145\/3088511","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,31]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}