The natural proofs barrier against data-structure lower-bounds [STOC’26]
Bruno Loff, Michal Koucký, Tulasimohan Molli, Michael Saks
@inproceedings{LKMS26, author = {Loff, Bruno and Koucký, Michal and Molli, Tulasimohan and Saks, Michael}, title = {The natural proofs barrier against data-structure lower-bounds}, booktitle = {58th Annual ACM Symposium on Theory of Computing (STOC)}, year = {2026} }
Consider a data structure problem with possible data coming from a set \mathcal D, queries coming from a set \mathcal Q, and in the dynamic case updates coming from a set \mathcal U. Then, the current state of the art in data structure lower bounds is t = \tilde\Omega(\log |\mathcal Q|) for static data structure problems, and \max(t_{\mathrm q},t_{\mathrm u}) = \tilde\Omega((\log n)^2) where n = \max(|\mathcal Q|,|\mathcal U|,\log |\mathcal D|) for dynamic.
We port Razborov and Rudich’s natural-proofs framework to the setting of static and dynamic data structures in the cell probe model, in a way that strongly suggests this state of the art is unlikely to be improved anytime soon. A similar direction was recently taken also by Korten, Pitassi and Impagliazzo (FOCS 2025) who look at static data structure lower bounds in a different regime of parameters. Our contribution is:
- We define notions analogous to pseudorandom functions (PRF). We call these primitives local PRFs, in the context of static data structures, and local and locally updatable (LLU) PRFs, in the context of dynamic data structures.
- We then formulate cryptographic conjectures, namely, that secure local PRFs and secure LLU PRFs exist, precisely at the frontier where we are no longer able to prove static, respectively dynamic, data structure lower bounds. If these conjectures are true, it follows that the current state of the art in data structure lower bounds cannot be improved by a natural proof.
- We show that (almost) every single known data structure lower bound proof is a natural proof, by surveying all lower bounds in the literature (known to us). (The only exception is proofs based on lifting theorems.)
- It follows that, if our cryptographic conjecture is true, then all known lower bound proof techniques (minus the one exception) are unable to improve upon the state of the art. (We also attempt to address the exception.)
- Further, we provide concrete candidate constructions for our two pseudo-ran-dom primitives. We conjecture that our constructions are secure for parameters just above the state-of-the-art lower bounds.
- We also show that, whether or not they are secure, our candidate PRFs at least satisfy the natural properties appearing in all (but one) known proofs.
- So if one is interested in improving upon the state of the art in static or dynamic data structure lower bounds, one must find a non-natural method of proving such lower bounds (no such method currently exists), or one may as well begin by trying to break our PRF candidates.
Criticality of AC0 formulae [CCC’23]
Prahladh Harsha, Tulasimohan Molli, Ashutosh Shankar
@inproceedings{HMS23, author = {Harsha, Prahladh and Molli, Tulasimohan and Shankar, Ashutosh}, title = {Criticality of AC0 formulae}, booktitle = {38th Computational Complexity Conference (CCC)}, year = {2023} }
A p-random restriction is a random partial input obtained by independently setting each variable to either 0,1 with (1-p)/2 each or leaving it unset with probability p. In this work, we study decision trees of bounded depth formulas under p-random restrictions.
Criticality of a boolean function f is defined to be the probability p at which the decision tree depth t of a random restriction of f goes down exponentially in t. Criticality has been implicitly studied in circuit complexity in the works of {all criticality results here}. The ground breaking work of Hastad’s switching lemma is a bound on criticality of CNFs and DNFs. Rossman defined the notion of criticality and showed its connection to average case lower bounds, fourier tail bounds, learning algorithms and decision tree size.
In this we work we show optimal bound on criticality of \AC^0 which for a formula of depth d+1 and size S is \bra{\frac{\log S}{d}}^d. Prior to this work, Rossman showed a similar bound for regular formulas: the class of \AC^0 formulas in which all gates at any given depth have the same fan-in. We extend their proof the general \AC^0 formulas.
Tight Chang’s lemma type bounds for Boolean functions [FSTTCS’21]
Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, Swagato Sanyal
@inproceedings{CMM21, author = {Chakraborty, Sourav and Mande, Nikhil S. and Mittal, Rajat and Molli, Tulasimohan and Paraashar, Manaswi and Sanyal, Swagato}, title = {Tight Chang’s lemma type bounds for Boolean functions}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)}, year = {2021} }
Chang’s lemma (Duke Mathematical Journal, 2002) is a classical result in mathematics, with applications spanning across additive combinatorics, combinatorial number theory, analysis of Boolean functions, communication complexity and algorithm design. For a Boolean function f that takes values in \pmone let r(f) denote its Fourier rank (i.e., the dimension of the span of its Fourier support). For each positive threshold t, Chang’s lemma provides a lower bound on \delta(f):=\Pr[f(x)=-1] in terms of the dimension of the span of its characters with Fourier coefficients of magnitude at least 1/t. In this work we examine the tightness of Chang’s lemma with respect to the following three natural settings of the threshold:
- the Fourier sparsity of f, denoted k(f),
- the Fourier max-supp-entropy of f, denoted k'(f), defined to be the maximum value of the reciprocal of the absolute value of a non-zero Fourier coefficient,
- the Fourier max-rank-entropy of f, denoted k''(f), defined to be the minimum t such that characters whose coefficients are at least 1/t in magnitude span a r(f)-dimensional space. In this work we prove new lower bounds on \delta(f) in terms of the above measures. One of our lower bounds, \delta(f)=\Omega\left(r(f)^2/(k(f) \log^2 k(f))\right), subsumes and refines the previously best known upper bound on r(f) in terms of k(f) by Sanyal (Theory of Computing, 2019). Another lower bound, \delta(f) =\Omega\left(r(f)/(\seerank(f) \log k(f))\right), is based on our improvement of a bound by Chattopadhyay, Hatami, Lovett and Tal (ITCS, 2019) on the sum of absolute values of level-1 Fourier coefficients in terms of \ftwo-degree. We further show that Chang’s lemma for the above-mentioned choices of the threshold is asymptotically outperformed by our bounds for most settings of the parameters involved.
Next, we show that our bounds are tight for a wide range of the parameters involved, by constructing functions witnessing their tightness. All the functions we construct are modifications of the Addressing function, where we replace certain input variables by suitable functions. Our final contribution is to construct Boolean functions f for which
- our lower bounds asymptotically match \delta(f), and
- for any choice of the threshold t, the lower bound obtained from Chang’s lemma is asymptotically smaller than \delta(f). Our results imply more refined deterministic one-way communication complexity upper bounds for XOR functions. Given the wide-ranging application of Chang’s lemma, we strongly feel that our refinements of Chang’s lemma will find many more applications.
Probabilistic degree of OR over the Reals [FSTTCS’18, RSA’21]
Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan
@article{BHMS21, author = {Bhandari, Siddharth and Harsha, Prahladh and Molli, Tulasimohan and Srinivasan, Srikanth}, title = {On the probabilistic degree of OR over the reals}, journal = {Random Struct. Algorithms}, volume = {59}, number = {1}, pages = {53–67}, year = {2021} }
We study the probabilistic degree over \reals of the \OR function on n variables. For \eps \in (0,1/3), the \eps-error probabilistic degree of any Boolean function f:\zo^n\to \zo over \reals is the smallest non-negative integer d such that the following holds: there exists a distribution \distP of polynomials P(x_1,\ldots,x_n) \in \reals[x_1,\ldots,x_n] of degree at most d such that for all \bar{x} \in \zo^n, we have \Pr_{P \sim \distP}[P(\bar{x}) = f(\bar{x}) ] \geq 1- \eps. It is known from the works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. 6th CCC 1991), that the \eps-error probabilistic degree of the \OR function is at most O(\log n \cdot \lepsinv). Our first observation is that this can be improved to \bigo{\ans} which is better for small values of \eps.
In all known constructions of probabilistic polynomials for the \OR function (including the above improvement), the polynomials P in the support of the distribution \distP have the following special structure:
[ P(x_1,,x_n) = 1 - _{i } (1- L_i(x_1,,x_n)), ]
where each L_i(x_1,\dots, x_n) is a linear form in the variables x_1,\ldots,x_n, i.e., the polynomial 1-P(\bar{x}) is a product of affine forms. We show that the \eps-error probabilistic degree of \OR when restricted to polynomials of the above form is \Omega\left( \ans/\log^2 \left( \ans \right)\right), thus matching the above upper bound (up to poly-logarithmic factors).
Cite
Presentation Preview
| Title | Authors | Venues |
|---|---|---|
| The natural proofs barrier against data-structure lower-bounds | Bruno Loff, Michal Koucký, Tulasimohan Molli, Michael Saks | STOC’26 |
| Criticality of AC0 formulae | Prahladh Harsha, Tulasimohan Molli, Ashutosh Shankar | CCC’23 |
| Tight Chang’s lemma type bounds for Boolean functions | Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, Swagato Sanyal | FSTTCS’21 |
| Probabilistic degree of OR over the Reals | Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan | FSTTCS’18, RSA’21 |