Paper Info
Title
Criticality of Regular Formulas.
Abstract
We define the criticality of a boolean function f : {0, 1}(n) -> {0, 1} as the minimum real number lambda >= 1 such that P [DTdepth(f vertical bar R-p) >= t] <= (p lambda)(t) for all p is an element of [0, 1] and t is an element of N, where R-p is the p-random restriction and DTdepth is decision-tree depth. Criticality is a useful parameter: it implies an O(2((1-1/2 lambda)n)) bound on the decision-tree size of f, as well as a 2(-Omega(k/lambda)) bound on Fourier weight of f on coefficients of size >= k. In an unpublished manuscript [11], the author showed that a combination of Hastad's switching and multi-switching lemmas [5, 6] implies that AC(0) 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(1/d log s)(d) bound for regular formulas: the class of AC(0) 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(0) circuits due to Impagliazzo, Matthews, Paturi [7] and Tal [17]. As a further corollary, we increase from o(log n/log log n) 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.
Year
DOI
Venue
2019
10.4230/LIPIcs.CCC.2019.1
Leibniz International Proceedings in Informatics
Keywords
Field
DocType
AC(0) circuits,formulas,criticality
Discrete mathematics,Algebra,Computer science,Criticality
Conference
Volume
ISSN
Citations 
137
1868-8969
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Benjamin Rossman144.28