{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:37:12Z","timestamp":1787341032066,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"name":"AUFF Starting Grant"},{"DOI":"10.13039\/501100007277","name":"Center for Massive Data Algorithmics","doi-asserted-by":"publisher","award":["DNRF84"],"award-info":[{"award-number":["DNRF84"]}],"id":[{"id":"10.13039\/501100007277","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>This paper proves the first superlogarithmic lower bounds on the cell probe complexity of dynamic Boolean (also known as decision) data structure problems, a long-standing milestone in data structure lower bounds. We introduce a new method for proving dynamic cell probe lower bounds and use it to prove an $\\tilde{\\Omega}({lg}^{1.5} \\ n)$ lower bound on the operational time of a wide range of Boolean data structure problems, most notably, on the query time of dynamic range counting over $\\mathbb{F}_2$ [M. Patrascu, Lower bounds for $2$-dimensional range counting, in STOC 2007, ACM, New York, 2007, pp. 40--46]. Proving an $\\omega({\\rm lg} \\ n)$ lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai P\u01cetra\u015fcu's obituary [M. Thorup, Bull. Eur. Assoc. Theor. Comput. Sci., 109 (2013), pp. 7--13]. This result also implies the first $\\omega({lg} \\ n)$ lower bound for the classical 2-dimensional (2D) range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases. We derive similar lower bounds for Boolean versions of dynamic polynomial evaluation and 2D rectangle stabbing, and for the (non-Boolean) problems of range selection and range median. Our technical centerpiece is a new way of \u201cweakly\u201d simulating dynamic data structures using efficient one-way communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebyshev) polynomials which may be of independent interest, and offers an entirely new algorithmic angle on the \u201ccell sampling\u201d method of Panigrahy, Talwar, and Wieder [ Lower bounds on near neighbor search via metric expansion, FOCS 2010, IEEE Computer Society, Los Alamitos, CA, 2010, pp. 805--814].<\/jats:p>","DOI":"10.1137\/18m1198429","type":"journal-article","created":{"date-parts":[[2020,3,12]],"date-time":"2020-03-12T10:19:16Z","timestamp":1584008356000},"page":"STOC18-323-STOC18-367","source":"Crossref","is-referenced-by-count":3,"title":["Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds"],"prefix":"10.1137","volume":"49","author":[{"given":"Kasper Green","family":"Larsen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Omri","family":"Weinstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huacheng","family":"Yu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,3,12]]},"reference":[{"key":"atypb1","first-page":"809","author":"Agarwal P. K.","year":"2004","journal-title":"Boca Raton, FL"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"H. Buhrman, R. Cleve, R. de Wolf, and C. Zalka,\n                      Bounds for small-error and zero-error quantum algorithms\n                      , in 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 1999, New York, IEEE Computer Society, Los Alamitos, CA, 1999, pp. 358-368.","DOI":"10.1109\/SFFCS.1999.814607"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.003"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"R. Clifford, A. Gr\u00f8nlund, and K. G. Larsen,\n                      New unconditional hardness results for dynamic and online problems\n                      , in Proceedings of the 56th IEEE Symposium on Foundations of Computer Science, IEEE, Piscataway, NJ, pp. 1089-1107, 2015.","DOI":"10.1109\/FOCS.2015.71"},{"key":"atypb6","first-page":"345","author":"Fredman M. L.","year":"1989","journal-title":"New York"},{"key":"atypb7","unstructured":"R. L. Graham, D. E. Knuth, and O. Patashnik,\n                      Concrete Mathematics: A Foundation for Computer Science\n                      , 2nd ed., Addison-Wesley Longman Publishing, Boston, MA, 1994."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.047"},{"key":"atypb9","first-page":"805","author":"J\u00f8rgensen A. G.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb10","first-page":"558","author":"J\u00e1J\u00e1 J.","year":"2004","journal-title":"Berlin"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"K. S. Kedlaya and C. Umans,\n                      Fast modular composition in any characteristic\n                      , in Proceedings of the 49th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2008, pp. 146-155.","DOI":"10.1109\/FOCS.2008.13"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213987"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"K. Green Larsen,\n                      Higher cell probe lower bounds for evaluating polynomials\n                      , in Proceedings of the 53rd IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2012, pp. 293-301.","DOI":"10.1109\/FOCS.2012.21"},{"key":"atypb14","unstructured":"K. Green Larsen,\n                      Models and Techniques for Proving Data Structure Lower Bounds\n                      , Ph.D thesis, Aarhus University, Aarhus, Denmark, 2013."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)80018-2"},{"key":"atypb16","first-page":"40","author":"Patrascu M.","year":"2007","journal-title":"New York"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"M. P\u01cetra\u015fcu,\n                      Unifying the landscape of cell-probe lower bounds\n                      , in Proceedings of the 49th IEEE Symposium on Foundations of Computer Science, 2008, pp. 434-443.","DOI":"10.1109\/FOCS.2008.69"},{"key":"atypb18","first-page":"20","author":"P\u01cetra\u015fcu M.","year":"2004","journal-title":"Philadelphia"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447256"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"R. Panigrahy, K. Talwar, and U. Wieder,\n                      Lower bounds on near neighbor search via metric expansion\n                      , in 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, IEEE Computer Society, Los Alamitos, CA, 2010, pp. 805-814.","DOI":"10.1109\/FOCS.2010.82"},{"key":"atypb21","first-page":"7","volume":"109","author":"Thorup M.","year":"2013","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"atypb23","first-page":"305","author":"Weinstein O.","year":"2016","journal-title":"NJ"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322274"},{"key":"atypb25","first-page":"2","author":"Yin Y.","year":"2010","journal-title":"ACM Trans. Comput. Theory"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1198429","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:02:30Z","timestamp":1787338950000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1198429"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M1198429"],"URL":"https:\/\/doi.org\/10.1137\/18m1198429","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}