Criticality of regular formulas

We define the criticality of a boolean function f : {0, 1}n → {0, 1} as the minimum real number λ ≥ 1 such that P DTdepth(fRp) ≥ t ≤ (pλ)t for all p ∈ [0, 1] and t ∈ N, where Rp is the p-random restriction and DTdepth is decision-tree depth. Criticality is a useful parameter: it implies an O(2(1− 21λ )n) bound on the decision-tree size of f, as well as a 2−Ω(k/λ) bound on Fourier weight of f on coefficients of size ≥ k. In an unpublished manuscript [11], the author showed that a combination of Håstad’s switching and multi-switching lemmas [5, 6] implies that AC0 circuits of depth d + 1 and size s have criticality at most O(log s)d. In the present paper, we establish a stronger O(d1 log s)d bound for regular formulas: the class of AC0 formulas in which all gates at any given depth have the same fan-in. This result is based on (i) a novel switching lemma for bounded size (unbounded width) DNF formulas, and (ii) an extension of (i) which analyzes a canonical decision tree associated with an entire depth-d formula. As corollaries of our criticality bound, we obtain an improved #SAT algorithm and tight Linial-Mansour-Nisan Theorem for regular formulas, strengthening previous results for AC0 circuits due to Impagliazzo, Matthews, Paturi [7] and Tal [17]. As a further corollary, we increase from o(logloglognn ) to o(log n) the number of quantifier alternations for which the QBF-SAT (quantified boolean formula satisfiability) algorithm of Santhanam and Williams [14] beats exhaustive search.

Duke Scholars

Author Benjamin Rossman Computer Science