Answers are grounded in this paper and cite their sources.
Rossman [In Proc.34th Comput. Complexity Conf., 2019] introduced the notion of criticality. The criticality of a Boolean function f : \0,1\ⁿ → \0,1\ is the minimum λ≥ 1 such that for all positive integers t, \[ ρ~ R_p[DTdepth(f|_ρ) ≥ t] ≤ (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 AC⁰-circuits against parity showed that the criticality of any AC⁰-circuit of size S and depth $d+1$ is at most O(log S)ᵈ and any regular AC⁰-formula of size S and depth $d+1$ is at most O(1d · log S)ᵈ. We strengthen these results by showing that the criticality of any AC⁰-formula (not necessarily regular) of size S and depth $d+1$ is at most O(1d· log S)ᵈ, resolving a conjecture due to Rossman. This result also implies Rossman's optimal lower bound on the size of any depth-d AC⁰-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 AC⁰-formulae.
No takes yet. Share an insight, caveat, or question.
Harsha et al. (2022) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: