Criticality of regular formulas

Conference Paper

We define the criticality of a boolean function f : {0, 1} → {0, 1} as the minimum real number λ ≥ 1 such that P DT (fRp) ≥ t ≤ (pλ) for all p ∈ [0, 1] and t ∈ N, where Rp is the p-random restriction and DT is decision-tree depth. Criticality is a useful parameter: it implies an O(2 ) 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 AC circuits of depth d + 1 and size s have criticality at most O(log s) . In the present paper, we establish a stronger O( log s) bound for regular formulas: the class of AC 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 AC circuits due to Impagliazzo, Matthews, Paturi [7] and Tal [17]. As a further corollary, we increase from o( ) 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. n t (1− 21λ )n − 0 d 1 d 0 0 log n depth depth d log log n

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