Criticality of AC0-formulae


Prahladh Harsha April 17, 2023.


Hastad’s celebrated switching lemma gives inverse-exponential bounds (In terms of t) on the probability that an k-DNF when hit by a p-restriction requires decision-trees of depth larger than t. The switching lemma has proved to be extremely powerful, since its discovery, leading to optimal size lower bounds for AC0-circuits [Hastad 1986] and AC0 formulae [Rossman 2015] against the parity function

More recently, the search for optimal correlation bounds against parity led to the notion of criticality [Rossman 2019]. The criticality of a Boolean function f : {0, 1}^n → {0, 1} is the minimum λ ≥ 1 such that for all positive integers t, we have

Pr_{ρ∼Rp} [ DT_depth (f _ρ) ≥ t ] ≤ (pλ)^t

Hastad (2014) proved that size S and depth (d+1) AC0-circuits have criticality at most O((log S)^d) leading to optimal correlation bounds of AC0-circuits against parity. Rossman (2019) subsequently proved that size S and depth (d+1) AC0-formulae, which are regular (ie., all gates of the same depth have equal fan-in) have criticality at most O(((log S)/d)^d).

In this work, we strengthen and unify all the above results by proving that any (not necessarily regular) AC0-formula of size S and depth (d+1) has criticality at most O(((log S)/d)^d). This criticality bound implies tight correlation bounds against parity, tight Fourier concentration results and improved #SAT algorithm for AC0-formulae.

[Joint work with Tulasimohan Molli and Ashutosh Shankar]

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • On the Probabilistic Degree of an n-variate Boolean Function
  • A better-than-3 log n depth lower bound for De Morgan formulas with restrictions on top gates
  • Are quantum speedups for learning expressive classes possible?
  • Improved Quantum Query Upper Bounds Based on Classical Decision Trees
  • Quantum Pseudoentanglement