An Ω ( ( log n / log log n ) 2 ) \Omega((\log n/\log\log n)^{2}) Cell-Probe Lower Bound for Dynamic Boolean Data Structures
Young Kun Ko · 2026
Read An Ω ( ( log n / log log n ) 2 ) \Omega((\log n/\log\log n)^{2}) Cell-Probe Lower Bound for Dynamic Boolean Data Structures by Young Kun Ko (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-25914.txt.
Description
Ko resolves a long-standing open problem on the hardness of dynamic Boolean data structures. He proves a lower bound of order log n over log log n, squared. The result covers the Multiphase Problem of Patrascu with inner product over the field of two elements. It matches the bound known for weighted problems since 2012. The key step is a new communication game with a verification round. In that round, Bob checks Alice's simulation against real memory. Ko argues the result likely marks the ceiling of the chronogram method.
Catalog record
| CREATOR | Young Kun Ko |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62763 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.25914