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

CREATORYoung Kun Ko
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62763
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.25914

Browse the full library · About the Tower of Babel