License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2019.1
URN: urn:nbn:de:0030-drops-108230
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10823/
Rossman, Benjamin
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 Pr [DT_{depth}(f|R_p) >= t] <= (p lambda)^t for all p in [0,1] and t in N, where R_p is the p-random restriction and DT_{depth} 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 [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.
BibTeX - Entry
@InProceedings{rossman:LIPIcs:2019:10823,
author = {Benjamin Rossman},
title = {{Criticality of Regular Formulas}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {1:1--1:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-116-0},
ISSN = {1868-8969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10823},
URN = {urn:nbn:de:0030-drops-108230},
doi = {10.4230/LIPIcs.CCC.2019.1},
annote = {Keywords: AC^0 circuits, formulas, criticality}
}
|
Keywords: |
|
AC^0 circuits, formulas, criticality |
|
Collection: |
|
34th Computational Complexity Conference (CCC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
16.07.2019 |
