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

Rossman [In \textit{Proc.34th Comput. Complexity Conf.}, 2019] introduced the notion of $\mathit{\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$, $$\underset{\rho \sim {\mathcal{R}}_p}{\mathrm{Pr}}[{\text{DT}}_{\text{depth}}(f{\mathrm{\mid }}_{\rho })\ge t]\le (p\lambda {)}^t\mathrm{.}$$ 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$-$\mathit{\text{circuit}}$ of size $S$ and depth $d+1$ is at most $O(\log S{)}^d$ and any $\mathit{\text{regular}}$ ${\text{AC}}^0$-$\mathit{\text{formula}}$ of size $S$ and depth $d+1$ is at most $O{(\frac{1}{d}\cdot \log S)}^d$. We strengthen these results by showing that the criticality of $\mathit{\text{any}}$ ${\text{AC}}^0$-formula (not necessarily regular) of size $S$ and depth $d+1$ is at most $O{(\frac{1}{d}\cdot \log S)}^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 [$\mathit{\text{Comput.}}\mathit{\text{Complexity,}}\mathit{\text{27(2):209–223,}}\mathit{\text{2018.}}$]. Our result implies tight correlation bounds against parity, tight Fourier concentration results and improved $\mathrm{\#}$SAT algorithm for ${\text{AC}}^0$-formulae.