{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:18Z","timestamp":1781078178820,"version":"3.54.1"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T00:00:00Z","timestamp":1646352000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR project DIGRAPHS","award":["ANR-19-CE48-0013-01"],"award-info":[{"award-number":["ANR-19-CE48-0013-01"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>\n            We show, assuming the Strong Exponential Time Hypothesis, that for every \u03b5 &gt; 0, approximating undirected unweighted\n            <jats:sc>Diameter<\/jats:sc>\n            on\n            <jats:italic>n<\/jats:italic>\n            -vertex\n            <jats:italic>m<\/jats:italic>\n            -edge graphs within ratio 7\/4 - \u03b5 requires\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>\n              4\/3 -\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            time, even when\n            <jats:italic>m<\/jats:italic>\n            = \u00d5(\n            <jats:italic>n<\/jats:italic>\n            ). This is the first result that conditionally rules out a near-linear time 5\/3-approximation for undirected\n            <jats:sc>Diameter<\/jats:sc>\n            .\n          <\/jats:p>","DOI":"10.1145\/3494540","type":"journal-article","created":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T11:32:35Z","timestamp":1646393555000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time\n            <i>n<\/i>\n            <sup>4\/3<\/sup>"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1653-5822","authenticated-orcid":false,"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[{"name":"Universit\u00e9 Lyon, CNRS, ENS de Lyon, Universit\u00e9 Claude Bernard Lyon 1, LIP UMR5668, Lyon, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,3,4]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303421"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188950"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2021.17"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch27"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840746"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.78"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2925416"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_10_2","unstructured":"Mina Dalirrooyfard Ray Li and Virginia Vassilevska Williams. 2021. Hardness of approximate diameter: Now for undirected graphs. arXiv:2106.06026. Retrieved from https:\/\/arxiv.org\/abs\/2106.06026."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451130"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_14_2","unstructured":"Ray Li. 2020. Improved SETH-hardness of unweighted diameter. arXiv2008.05106. Retrieved from https:\/\/arxiv.org\/abs\/2008.05106."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451045"},{"key":"e_1_3_2_16_2","first-page":"41","article-title":"Lower bounds based on the exponential time hypothesis","volume":"105","author":"Lokshtanov Daniel","year":"2011","unstructured":"Daniel Lokshtanov, D\u00e1niel Marx, and Saket Saurabh. 2011. Lower bounds based on the exponential time hypothesis. Bull. EATCS 105 (2011), 41\u201372.","journal-title":"Bull. EATCS"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3374857.3374870"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_3_2_20_2","first-page":"3431","volume-title":"Proceedings of the International Conference on Microelectronics (ICM\u201918)","volume":"3","author":"Williams Virginia Vassilevska","year":"2018","unstructured":"Virginia Vassilevska Williams. 2018. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Conference on Microelectronics (ICM\u201918), Vol. 3. World Scientific, Singapore, 3431\u20133472."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494540","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3494540","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:43Z","timestamp":1750193323000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494540"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,4]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3494540"],"URL":"https:\/\/doi.org\/10.1145\/3494540","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,4]]},"assertion":[{"value":"2021-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}