2026-07-26T16:23:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18289 2024-03-06T11:01:31Z ddc:004 open_access

Criticality of AC⁰-Formulae Harsha, Prahladh Molli, Tulasimohan Shankar, Ashutosh AC⁰ circuits AC⁰ formulae criticality switching lemma correlation bounds 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 and all p ∈ [0,1], Pr_{ρ∼ℛ_p}[DT_{depth}(f|_ρ) ≥ t] ≤ (pλ)^t, where ℛ_p refers to the distribution of p-random restrictions. 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)^d and any regular AC⁰-formula of size S and depth d+1 is at most O((1/d)⋅log S)^d. 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((log S)/d)^d, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prahladh Harsha and Tulasimohan Molli and Ashutosh Shankar 2023 Is Part Of LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2023.19 urn:nbn:de:0030-drops-182898 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.19 eng https://creativecommons.org/licenses/by/4.0/legalcode