{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:31:00Z","timestamp":1787340660605,"version":"build-2736575974"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"DFF Sapere Aude Research Leader","award":["9064-00068B"],"award-info":[{"award-number":["9064-00068B"]}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["AWD1007164"],"award-info":[{"award-number":["AWD1007164"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>In this work, we prove an [Formula: see text] unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in [Formula: see text]-node directed acyclic graphs under edge insertions. This is the first super-logarithmic lower bound for any natural graph problem. In proving the lower bound, we also make novel contributions to the state-of-the-art data structure lower bound techniques that we hope may lead to further progress in proving lower bounds.<\/jats:p>","DOI":"10.1137\/24m1638215","type":"journal-article","created":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T04:26:41Z","timestamp":1739420801000},"page":"FOCS23-42-FOCS23-69","source":"Crossref","is-referenced-by-count":0,"title":["Super-Logarithmic Lower Bounds for Dynamic Graph Problems"],"prefix":"10.1137","volume":"55","author":[{"given":"Kasper Green","family":"Larsen","sequence":"first","affiliation":[{"name":"Department of Computer Science, Aarhus University, Aarhus, Denmark."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1450-1896","authenticated-orcid":true,"given":"Huacheng","family":"Yu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Princeton University, Princeton, NJ, 08540 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,2,13]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1145\/3563393"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"A. Abboud, J. Li, D. Panigrahi, and T. Saranurak, All-pairs max-flow is no harder than single-pair max-flow: Gomory-Hu trees in almost-linear time, in 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 2023, pp. 2204\u20132212.","DOI":"10.1109\/FOCS57990.2023.00137"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00063"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"S. Bhattacharya, P. Kiss, and T. Saranurak, Dynamic \\((1 + \\varepsilon)\\)-approximate matching size in truly sublinear update time, in 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 2023, pp. 1563\u20131588.","DOI":"10.1109\/FOCS57990.2023.00095"},{"key":"ref5","unstructured":"K. Bringmann, A. Gr\u00f8nlund, M. K\u00fcnnemann, and K. G. Larsen, The NFA Acceptance hypothesis: Non-combinatorial and dynamic lower bounds, in 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), LIPIcs. Leibniz Int. Proc. Inform. 287, V. Guruswami, ed. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany, 2024, pp. 22:1\u201322:25."},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00064"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"R. Clifford, A. Gr\u00f8nlund, and K. G. Larsen, New unconditional hardness results for dynamic and online problems, in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 2015, pp. 1089\u20131107.","DOI":"10.1109\/FOCS.2015.71"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"M. L. Fredman and M. E. Saks, The cell probe complexity of dynamic data structures, in Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), ACM, 1989, pp. 345\u2013354.","DOI":"10.1145\/73007.73040"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"M. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak, Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture, in Proceedings of the 2015 ACM Symposium on Theory of Computing (STOC), ACM, 2015, pp. 21\u201330.","DOI":"10.1145\/2746539.2746609"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"K. G. Larsen, The cell probe complexity of dynamic range counting, in Proceedings of the 44th Symposium on Theory of Computing (STOC), ACM, 2012, pp. 85\u201394.","DOI":"10.1145\/2213977.2213987"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"K. G. Larsen, Higher cell probe lower bounds for evaluating polynomials, in 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 2012, pp. 293\u2013301.","DOI":"10.1109\/FOCS.2012.21"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/18M1198429"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90159-7"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"R. Panigrahy, K. Talwar, and U. Wieder, Lower bounds on near neighbor search via metric expansion, in 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS), 2010, pp. 805\u2013814.","DOI":"10.1109\/FOCS.2010.82"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"M. P\u01cetra\u015fcu, Towards polynomial lower bounds for dynamic problems, in Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), ACM, New York, 2010, pp. 603\u2013610, https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806772.","DOI":"10.1145\/1806689.1806772"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/09075336X"},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"M. P\u01cetra\u015fcu, Lower bounds for \\(\\,2\\)-dimensional range counting, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 2007, pp. 40\u201346.","DOI":"10.1145\/1250790.1250797"},{"key":"ref19","unstructured":"M. P\u01cetra\u015fcu and E. D. Demaine, Tight bounds for the partial-sums problem, in Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York; SIAM, Philadelphia, 2004, pp. 20\u201329."},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"M. P\u01cetra\u015fcu and M. Thorup, Higher lower bounds for near-neighbor and further rich problems, in 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 646\u2013654.","DOI":"10.1109\/FOCS.2006.35"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"M. P\u01cetra\u015fcu and M. Thorup, Don\u2019t rush into a union: Take time to find your roots, in Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), ACM, New York, 2011, pp. 559\u2013568.","DOI":"10.1145\/1993636.1993711"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701386216"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322274"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1638215","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:43:08Z","timestamp":1787337788000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1638215"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,13]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1137\/24M1638215"],"URL":"https:\/\/doi.org\/10.1137\/24m1638215","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,13]]}}}