Static data structures: an ω(log n) cell-probe lower bound for an explicit problem at linear space
Difficulty 76.5: the static bound has been stuck at Θ(log n) for linear space for over a decade while the dynamic barrier fell twice (2017, 2026), and the rigidity connection shows that strong versions are at least as hard as explicit-rigidity problems; it sits below log-rank (80) and Valiant rigidity (79.5), above ACC⁰ lower bounds (72). Application value 4.5: little practical consequence, just under log-rank (5.5). Leverage 41.5: it would reshape data-structure lower bounds and feed the rigidity programme, between ACC⁰ (45) and the feature-learning exponents (40).
The problem
Show that some lookup task needs more than about log n memory reads per question when memory barely exceeds the data.
- 1Data structure answers questions fast
- 2Cost: how many memory cells read
- 3Best proof: about log n reads needed
- 4No explicit task proven to need more
- 5Open: an explicit task needing more
The model. In the cell-probe model, a static data structure for a problem with a database of size and possible queries stores cells of bits each. A query is answered by reading () cells, adaptively, with all other computation free. So lower bounds are information-theoretic and apply to any algorithm.
Built from
earlier problems → this oneThe problems this one is built from: progress or tools it needs (builds on), special cases that come first (generalizes), and weaker results on the way (implies). On the right, what builds on it.
- Start with
- Step 2
- Explicit Valiant-rigid matrices: construct N×N matrices with rigidity N^(1+δ) at rank εNComplexity Theory · D79.5
- Then
- Static data structures: an ω(log n) cell-probe lower bound for an explicit problem at linear spaceThis problem
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- Communication complexity and cell-probe lower boundsTheory · host
- Then
- Static data structures: an ω(log n) cell-probe lower bound for an explicit problem at linear spaceThe problem
State of the art
Larsen (FOCS 2012, 'Higher cell probe lower bounds for evaluating polynomials') proved t = Ω(lg|F| / lg(Sw/(n lg|F|))) for polynomial evaluation over a field F with |F| ≥ n^{1+Ω(1)}, which is Ω(log n) at linear space and still the highest static bound. Earlier communication-based methods (Miltersen–Nisan–Safra–Wigderson) give only Ω(1) for poly(n) queries, and Pătraşcu–Thorup's refinement cannot exceed Ω(lg d / lg lg d) for d queries; Larsen's cell-sampling technique beats that by a log log factor and stops at the same scale. Dvir, Golovnev and Weinstein (arXiv:1811.02725, STOC 2019) call an ω(log n) bound at linear space 'a major open problem' and show why it is hard: for linear data structures, a bound of ω(log² n) at space (1+ε)n would give new P^NP rigid matrices, and polynomial bounds at near-optimal space would give log-depth linear-circuit lower bounds via Valiant's rigidity route (see also Natarajan Ramamoorthy–Rashtchian, arXiv:1910.11921). For dynamic data structures the logarithmic barrier has fallen: Larsen, Weinstein and Yu (arXiv:1703.03575, STOC 2018) proved Ω̃(log^{1.5} n) for dynamic Boolean problems, and Ko (arXiv:2603.25914, revised September 2026, to appear at FOCS 2026 per its arXiv comment) proved Ω((log n / log log n)²), which the author argues is the ceiling of the chronogram framework. Weinstein and Yu (arXiv:1604.03030) showed that a slight strengthening of their amortized dynamic bound for 2D weighted range counting would give Ω((log n / log log n)²) for static 3D orthogonal range counting at near-linear space, but that strengthening is unproven. No explicit static problem is known to need ω(log n) probes at linear space.
Realistic applications
Mostly foundational. Static lower bounds mark where range-searching, membership and predecessor structures cannot be improved; at the strength of polynomial bounds they would also yield circuit lower bounds via matrix rigidity.
What counts as solved
A proof, accepted by experts, that an explicit static problem with poly(n) queries requires t = ω(log n) probes for every cell-probe data structure with O(n) cells of O(log n) bits. Conditional results (e.g. assuming a strengthened dynamic bound) and bounds only for restricted (e.g. linear or non-adaptive) data structures do not count.
How it gets verified
Expert reviewOnly expert review of the argument is possible today.
The target is an omega(log n) cell-probe lower bound for an explicit static problem at linear space. The cell-probe model is not in Mathlib, so the lower bound cannot be machine-checked today. Experts review the proof, and conditional or restricted-model results do not count.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
Needs new communication-complexity or information-theoretic arguments; no experimental component.
Bottlenecks
ranked by votes- #1TheoryCommunication and cell-sampling methods stop at log(m/n)/log(S/n)
Every known static technique (asymmetric communication, Pătraşcu–Thorup's refinement, Larsen's cell sampling) yields at most about log(m/n)/log(S/n) probes, i.e. Θ(log n) at linear space with poly(n) queries; a super-logarithmic bound needs an argument that is not a one-round information count.
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Mar 26, 2026Ω((log n / log log n)²) for dynamic Boolean problems (preprint)source
Ko's argument, which the author says is the limit of the chronogram framework.
- Nov 5, 2018Static lower bounds imply rigiditysource
Dvir, Golovnev and Weinstein explain the static barrier: strong enough bounds for linear data structures yield rigid matrices (arXiv month; day approximate).
- Mar 10, 2017First super-logarithmic dynamic Boolean lower boundsource
Larsen, Weinstein and Yu prove Ω̃(log^{1.5} n) for dynamic problems over F₂.
- Apr 11, 2016Dynamic-to-static route for range countingsource
Weinstein and Yu show a strengthened amortized dynamic bound would imply a super-logarithmic static bound for 3D range counting.
- Oct 20, 2012Ω(log n) static bound for polynomial evaluation