Criticality of ${\text{AC}}^0$ formulae

Abstract

Rossman [In $\textit{Proc. $34$th Comput. Complexity Conf.}$, 2019] introduced the notion of $\text{criticality}$. The criticality of a Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is the minimum $\lambda \ge 1$ such that for all positive integers $t$, \[ \Pr_{ρ\sim \mathcal{R}_p}\left[\text{DT}_{\text{depth}}(f|_ρ) \geq t\right] \leq (pλ)^t. \] Hästad's celebrated switching lemma shows that the criticality of any $k$-DNF is at most $O(k)$. Subsequent improvements to correlation bounds of ${\text{AC}}^0$-circuits against parity showed that the criticality of any ${\text{AC}}^0$-$\text{circuit}$ of size $S$ and depth $d+1$ is at most $O(\log S{)}^d$ and any $\text{regular}$ ${\text{AC}}^0$-$\text{formula}$ of size $S$ and depth $d+1$ is at most $O{\left(\frac{1}{d}\cdot \log S\right)}^d$. We strengthen these results by showing that the criticality of $\text{any}$ ${\text{AC}}^0$-formula (not necessarily regular) of size $S$ and depth $d+1$ is at most $O{\left(\frac{1}{d}\cdot \log S\right)}^d$, resolving a conjecture due to Rossman. This result also implies Rossman's optimal lower bound on the size of any depth-$d$ ${\text{AC}}^0$-formula computing parity [$\text{Comput. Complexity, 27(2):209–223, 2018.}$]. Our result implies tight correlation bounds against parity, tight Fourier concentration results and improved $\#$SAT algorithm for ${\text{AC}}^0$-formulae.