  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.

Computational Complexity