Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
Kasper Green Larsen, Omri Weinstein, Huacheng Yu · 2018
This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.