文章基本信息

标题：Criticality of Regular Formulas
本地全文：下载
作者：rossman:LIPIcs: : , author {Benjamin Rossman
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：137
页码：1-28
DOI：10.4230/LIPIcs.CCC.2019.1
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We define the criticality of a boolean function f : {0,1}^n -> {0,1} as the minimum real number lambda >= 1 such that Pr [DT_{depth}(f R_p) >= t] = k. In an unpublished manuscript [Rossmann, 2018], the author showed that a combination of Håstad's switching and multi-switching lemmas [Håstad, 1986; Håstad, 2014] 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 [Impagliazzo et al., 2012] and Tal [Tal, 2017]. 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 [Santhanam and Williams, 2014] beats exhaustive search.
关键词：AC^0 circuits; formulas; criticality