Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR22-182 | 5th January 2023 06:33

Criticality of AC0-Formulae

RSS-Feed




Revision #1
Authors: Prahladh Harsha, Tulasi mohan Molli, A. Shankar
Accepted on: 5th January 2023 06:33
Downloads: 154
Keywords: 


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.


Paper:

TR22-182 | 16th December 2022 09:31

Criticality of AC0-Formulae





TR22-182
Authors: Prahladh Harsha, Tulasi mohan Molli, A. Shankar
Publication: 16th December 2022 09:31
Downloads: 300
Keywords: 


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.



ISSN 1433-8092 | Imprint