Criticality of regular formulas

Published

Conference Paper

© Benjamin Rossman; licensed under Creative Commons License CC-BY 34th Computational Complexity Conference (CCC 2019). 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.

Full Text

Duke Authors

Cited Authors

  • Rossman, B

Published Date

  • July 1, 2019

Published In

Volume / Issue

  • 137 /

International Standard Serial Number (ISSN)

  • 1868-8969

International Standard Book Number 13 (ISBN-13)

  • 9783959771160

Digital Object Identifier (DOI)

  • 10.4230/LIPIcs.CCC.2019.1

Citation Source

  • Scopus