Rossman [In $\textit{ Proc. $34$th Comput. Complexity Conf.}$, 2019] introduced the notion of $\textit{ criticality}$. The criticality of a Boolean function $f : \{ 0,1\}^n \to \{ 0,1\}$ is the minimum $\lambda \geq 1$ such that for all positive integers $t$, \[ \Pr_{ \rho \sim \mathcal{ R}_p}\left[\text{ DT}_{ \text{ depth}}(f|_{ \rho}) \geq t\right] \leq (p\lambda)^t. \] H\"astad'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$-$\textit{ circuit}$ of size $S$ and depth $d+1$ is at most $O(\log S)^d$ and any $\textit{ regular}$ $\text{ AC}^0$-$\textit{ formula}$ of size $S$ and depth $d+1$ is at most $O\left(\frac1d \cdot \log S\right)^d$. We strengthen these results by showing that the criticality of $\textit{ any}$ $\text{ AC}^0$-formula (not necessarily regular) of size $S$ and depth $d+1$ is at most $O\left(\frac1d\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 [$\textit{ 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.
Categories: cs.CC
