Rossman [In Proc. 34th Comput. Complexity Conf., 2019] introduced the notion of 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 R_p} [\text{DT}_{\text{depth}}(f|_\rho) \geq t] \leq (p\lambda)^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 AC0-circuits against parity showed that the criticality of any AC0-circuit of size $S$ and depth $d + 1$ is at most $O(\log S)^d$ and any regular AC0-formula of size $S$ and depth $d + 1$ is at most $O( \frac1d \cdot \log S)^d$. We strengthen these results by showing that the criticality of any AC0-formula (not necessarily regular) of size $S$ and depth $d + 1$ is at most $O(\frac1d\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 AC0-formula computing parity [Comput. Complexity, 27(2):209–223, 2018.]. Our result implies tight correlation bounds against parity, tight Fourier concentration results and improved #SAT algorithm for AC0-formulae.

This revised version fixes an issue in the previous version and has more detailed proofs.

Rossman [In Proc. 34th Comput. Complexity Conf., 2019] introduced the notion of 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 R_p} [\text{DT}_{\text{depth}}(f|_\rho) \geq t] \leq (p\lambda)^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 AC0-circuits against parity showed that the criticality of any AC0-circuit of size $S$ and depth $d + 1$ is at most $O(\log S)^d$ and any regular AC0-formula of size $S$ and depth $d + 1$ is at most $O( \frac1d \cdot \log S)^d$. We strengthen these results by showing that the criticality of any AC0-formula (not necessarily regular) of size $S$ and depth $d + 1$ is at most $O(\frac1d\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 AC0-formula computing parity [Comput. Complexity, 27(2):209–223, 2018.]. Our result implies tight correlation bounds against parity, tight Fourier concentration results and improved #SAT algorithm for AC0-formulae.