Revision #1 to TR22-182 | 5th January 2023 06:33
Criticality of AC0-Formulae
Abstract:
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.
Changes to previous version:
This revised version fixes an issue in the previous version and has more detailed proofs.
TR22-182 | 16th December 2022 09:31
Criticality of AC0-Formulae
Abstract:
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.
