{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:43:31Z","timestamp":1787496211541,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["DGE - 1656518"],"award-info":[{"award-number":["DGE - 1656518"]}]},{"DOI":"10.13039\/100000008","name":"David and Lucile Packard Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000008","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451045","type":"proceedings-article","created":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T21:26:13Z","timestamp":1623792373000},"page":"1684-1696","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH)"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3441-2364","authenticated-orcid":false,"given":"Ray","family":"Li","sequence":"first","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1_7"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303421"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.4"},{"key":"e_1_3_2_1_4_1","unstructured":"Amir Abboud Robert Krauthgamer and Ohad Trabelsi Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graph. arXiv preprint arXiv:2012.10281."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188950"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.033"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17402-6_5"},{"key":"e_1_3_2_1_9_1","volume-title":"Symposium on Theoretical Aspects of Computer Science, STACS","author":"Bonnet Edouard","year":"2021","unstructured":"Edouard Bonnet. Inapproximability of Diameter in super-linear time: Beyond the 5\/3 ratio. In Symposium on Theoretical Aspects of Computer Science, STACS 2021."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.02.033"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1062400"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00680-z"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00281-X"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch27"},{"key":"e_1_3_2_1_15_1","first-page":"349","volume-title":"Katina Russell. Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020","author":"Cao Nairen","year":"2020","unstructured":"Nairen Cao, Jeremy T. Fineman, and Katina Russell. Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 336\u2013349, 2020."},{"key":"e_1_3_2_1_16_1","first-page":"513","volume-title":"Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"Cao Nairen","year":"2020","unstructured":"Nairen Cao, Jeremy T. Fineman, and Katina Russell. Brief Announcement: Improved Work Span Tradeoff for Single Source Reachability and Approximate Shortest Paths. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), July, 2020, pages 511\u2013513."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840746"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.78"},{"key":"e_1_3_2_1_19_1","first-page":"355","volume-title":"Proc. SODA","author":"Chepoi Victor","year":"2002","unstructured":"Victor Chepoi, Feodor Dragan, and Yann Vax\u00e8s. Center and diameter problems in plane triangulations and quadrangulations. In Proc. SODA, pp. 346\u2013355, 2002."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331610"},{"key":"e_1_3_2_1_21_1","volume-title":"Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. ACM Transactions on Algorithms (TALG), 15(3): 1\u201357","author":"Coudert David","year":"2019","unstructured":"David Coudert, Guillaume Ducoffe, and Alexandru Popa. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. ACM Transactions on Algorithms (TALG), 15(3): 1\u201357, 2019."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736283"},{"key":"e_1_3_2_1_23_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019","author":"Dalirrooyfard Mina","year":"2019","unstructured":"Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, and Yuancheng Yu. Approximation algorithms for min-distance problems. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages 46:1\u201346:14, 2019."},{"key":"e_1_3_2_1_24_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019","author":"Dalirrooyfard Mina","year":"2019","unstructured":"Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, and Nicole Wein. Tight approximation algorithms for bichromatic graph diameter and related problems. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages 47:1\u201347:15, 2019."},{"key":"e_1_3_2_1_25_1","volume-title":"Dalirrooyfard and Nicole Wein. Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs. In Symposium on Theory of Computing, STOC","author":"Mina","year":"2021","unstructured":"Mina Dalirrooyfard and Nicole Wein. Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs. In Symposium on Theory of Computing, STOC 2021, to appear."},{"key":"e_1_3_2_1_26_1","first-page":"384","volume-title":"International Workshop on Combinatorial Algorithms","unstructured":"Peter, Damaschke. Computing giant graph diameters. In International Workshop on Combinatorial Algorithms, pp. 373\u2013384. Springer, Cham, 2016."},{"key":"e_1_3_2_1_27_1","volume-title":"Ducoffe, A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019","author":"Guillaume","year":"2019","unstructured":"Guillaume Ducoffe, A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019."},{"key":"e_1_3_2_1_28_1","first-page":"1922","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Ducoffe Guillaume","unstructured":"Guillaume Ducoffe, Michel Habib, and Laurent Viennot. Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1905\u20131922. Society for Industrial and Applied Mathematics, 2020."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(80)90039-6"},{"key":"e_1_3_2_1_31_1","first-page":"514","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Gawrychowski Pawl","unstructured":"Pawl Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, and Oren Weimann. Voronoi diagrams on planar graphs, and computing the diameter in deterministic $\\tilde O(n^5\/3)$ time. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 495\u2013514. Society for Industrial and Applied Mathematics, 2018. \\balance"},{"key":"e_1_3_2_1_32_1","volume-title":"On promise problems: A survey. Theoretical computer science","author":"Goldreich Oded","year":"2006","unstructured":"Oded Goldreich, On promise problems: A survey. Theoretical computer science. Springer, Berlin, Heidelberg, 254\u2013290, 2006."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_1_34_1","volume-title":"Aaron Sidford. Parallel Reachability in Almost Linear Work and Square Root Depth. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE","author":"Jambulapati Arun","year":"2019","unstructured":"Arun Jambulapati, Yang Liu, and Aaron Sidford. Parallel Reachability in Almost Linear Work and Square Root Depth. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2019."},{"key":"e_1_3_2_1_35_1","volume-title":"Avenues and Algorithmic Progress. In 26th Annual European Symposium on Algorithms (ESA 2018)","author":"K\u00fcnnemann Marvin","year":"2018","unstructured":"Marvin K\u00fcnnemann, On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress. In 26th Annual European Symposium on Algorithms (ESA 2018), 2018."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_1_37_1","unstructured":"Ray Li. Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH) arXiv preprint arXiv:2008.05106."},{"key":"e_1_3_2_1_38_1","first-page":"11","volume-title":"2016 International Computer Symposium (ICS)","author":"Lin Ting-Chun","unstructured":"Ting-Chun Lin, Mei-Jin Wu, Wei-Jie Chen, and Bang-Ye Wu. Computing the diameters of huge social networks. In 2016 International Computer Symposium (ICS), pages 6\u201311. IEEE, 2016."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2010.09.009"},{"key":"e_1_3_2_1_40_1","first-page":"672","volume-title":"39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II","author":"Peleg David","year":"2012","unstructured":"David Peleg, Liam Roditty, and Elad Tal. Distributed algorithms for network diameter and girth. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II, pages 660\u2013672, 2012."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00402-X"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702419650"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3374857.3374870"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_3_2_1_48_1","first-page":"898","volume-title":"Proceedings of the forty-fourth annual ACM symposium on Theory of computing","author":"Williams Virginia Vassilevska","unstructured":"Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 887\u2013898. ACM, 2012."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591811"},{"key":"e_1_3_2_1_50_1","first-page":"17","volume-title":"31st Conference on Computational Complexity, CCC 2016","author":"Williams Richard Ryan","year":"2016","unstructured":"Richard Ryan Williams. Strong ETH breaks with merlin and arthur: Short non-interactive proofs of batch evaluation. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 2:1\u20132:17, 2016."},{"key":"e_1_3_2_1_51_1","volume-title":"Proceedings of the ICM","volume":"3","author":"Williams Virginia Vassilevska","year":"2018","unstructured":"Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the ICM, volume 3. World Scientific, 2018."}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451045","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451045","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:01:44Z","timestamp":1750183304000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":50,"alternative-id":["10.1145\/3406325.3451045","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451045","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}