{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T22:09:42Z","timestamp":1766268582984,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":35,"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:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1740519, CCF-1909429, CCF-1514339"],"award-info":[{"award-number":["CCF-1740519, CCF-1909429, 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":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451130","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1697-1710","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Tight conditional lower bounds for approximating diameter in directed graphs"],"prefix":"10.1145","author":[{"given":"Mina","family":"Dalirrooyfard","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicole","family":"Wein","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884463"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303421"},{"key":"e_1_3_2_1_3_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Ancona Bertie","year":"2019","unstructured":"Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, and Nicole Wein. 2019. Algorithms and Hardness for Diameter in Dynamic Graphs. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188950"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17402-6_5"},{"key":"e_1_3_2_1_6_1","volume-title":"Inapproximability of Diameter in super-linear time: Beyond the 5\/3 ratio. arXiv preprint arXiv:2008.11315","author":"Bonnet Edouard","year":"2020","unstructured":"\\'Edouard Bonnet. 2020. Inapproximability of Diameter in super-linear time: Beyond the 5\/3 ratio. arXiv preprint arXiv:2008.11315, 2020."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.02.033"},{"volume-title":"Network analysis: methodological foundations. 3418","author":"Brandes Ulrik","key":"e_1_3_2_1_8_1","unstructured":"Ulrik Brandes. 2005. Network analysis: methodological foundations. 3418, Springer Science & Business Media."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch27"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.3390\/a13090216"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.78"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30850-5_10"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736283"},{"key":"e_1_3_2_1_14_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Dalirrooyfard Mina","year":"2019","unstructured":"Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, and Nicole Wein. 2019. Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)."},{"key":"e_1_3_2_1_15_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Dalirrooyfard Mina","year":"2019","unstructured":"Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, and Yuancheng Yu. 2019. Approximation Algorithms for Min-Distance Problems. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.91"},{"key":"e_1_3_2_1_17_1","volume-title":"Improved Hardness of Approximation of Diameter in the CONGEST Model. In 34th International Symposium on Distributed Computing (DISC","author":"Grossman Ofer","year":"2020","unstructured":"Ofer Grossman, Seri Khoury, and Ami Paz. 2020. Improved Hardness of Approximation of Diameter in the CONGEST Model. In 34th International Symposium on Distributed Computing (DISC 2020)."},{"key":"e_1_3_2_1_18_1","first-page":"564","volume-title":"Proc. 28th International Symposium on Distributed Computing (DISC","author":"Holzer Stephan","year":"2014","unstructured":"Stephan Holzer, David Peleg, Liam Roditty, and Roger Wattenhofer. 2014. Brief announcement: Distributed 3\/2-approximation of the diameter. In Proc. 28th International Symposium on Distributed Computing (DISC 2014). Pages 562\u2013564."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405719"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212744"},{"key":"e_1_3_2_1_22_1","volume-title":"Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH). arXiv preprint arXiv:2008.05106","author":"Ray Li.","year":"2020","unstructured":"Ray Li. 2020. Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH). arXiv preprint arXiv:2008.05106, 2020."},{"volume-title":"Computing the Diameters of Huge Social Networks. In 2016 International Computer Symposium (ICS). Pages 6\u201311","author":"Lin T. C.","key":"e_1_3_2_1_23_1","unstructured":"T. C. Lin, M. J. Wu, W. J. Chen, and B. Y. Wu. 2016. Computing the Diameters of Huge Social Networks. In 2016 International Computer Symposium (ICS). Pages 6\u201311."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1455266"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"David Peleg Liam Roditty and Elad Tal. 2012. Distributed algorithms for network diameter and girth. In International Colloquium on Automata Languages and Programming. Pages 660\u2013672.","DOI":"10.1007\/978-3-642-31585-5_58"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00402-X"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702419650"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3374857.3374870"},{"key":"e_1_3_2_1_30_1","first-page":"1995","article-title":"On the all-pairs-shortest-path problem in unweighted undirected graphs","volume":"51","author":"Seidel R.","year":"1995","unstructured":"R. Seidel. 1995. On the all-pairs-shortest-path problem in unweighted undirected graphs. JCSS, 51, 1995. Pages 400\u2013403.","journal-title":"JCSS"},{"key":"e_1_3_2_1_31_1","first-page":"0717","volume-title":"Proceedings of the 20th ACM International Conference on Information and Knowledge Management. CIKM '11. Pages 1191\u20131196","author":"Frank","unstructured":"Frank W. Takes and Walter A. Kosters. 2011. Determining the Diameter of Small World Networks. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management. CIKM '11. Pages 1191\u20131196. isbn:978-1-4503-0717-8"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00035"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591811"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567114"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"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.3451130","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451130","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451130","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451130"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":35,"alternative-id":["10.1145\/3406325.3451130","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451130","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"}}]}}