The natural proofs barrier against data-structure lower-bounds [STOC’26]
Bruno Loff, Michal Koucký, Tulasimohan Molli, Michael Saks
No matching items
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: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.
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.
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} }
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 whichOur 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.
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 ({} 1993) and Beigel, Reingold, and Spielman ({} 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} % \bigo{\log {\genfrac{(}{)}{0pt}{}{n}{\lepsinv}}} 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).
| 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 |