Math @ Duke

Publications [#348666] of Benjamin Rossman
Papers Published
 Rossman, B, Criticality of regular formulas,
Leibniz International Proceedings in Informatics, Lipics, vol. 137
(July, 2019), ISBN 9783959771160 [doi]
(last updated on 2022/05/19)
Abstract: 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 prandom restriction and DTdepth is decisiontree depth. Criticality is a useful parameter: it implies an O(2(1− 21λ )n) bound on the decisiontree 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 multiswitching 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 fanin. 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 depthd formula. As corollaries of our criticality bound, we obtain an improved #SAT algorithm and tight LinialMansourNisan 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 QBFSAT (quantified boolean formula satisfiability) algorithm of Santhanam and Williams [14] beats exhaustive search.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

