Criticality of Regular Formulas

Author Benjamin Rossman



PDF
Thumbnail PDF

File

LIPIcs.CCC.2019.1.pdf
  • Filesize: 0.67 MB
  • 28 pages

Document Identifiers

Author Details

Benjamin Rossman
  • Departments of Mathematics and Computer Science, University of Toronto, Canada

Acknowledgements

I am grateful to Prahladh Harsha, Shrikanth Srinivasan, Siddharth Bhandari, Tulasi Molli and Or Meir for valuable feedback on a preliminary version of this paper.

Cite AsGet BibTex

Benjamin Rossman. Criticality of Regular Formulas. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 1:1-1:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.CCC.2019.1

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • AC^0 circuits
  • formulas
  • criticality

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Kazuyuki Amano. Tight Bounds on the Average Sensitivity of k-CNF. Theory of Computing, 7(1):45-48, 2011. Google Scholar
  2. Paul Beame. A switching lemma primer. Technical report, Technical Report UW-CSE-95-07-01, Department of Computer Science and Engineering, University of Washington, 1994. Google Scholar
  3. Paul Beame, Russell Impagliazzo, and Srikanth Srinivasan. Approximating AC⁰ by Small Height Decision Trees and a Deterministic Algorithm for #AC⁰-SAT. In 27th Annual IEEE Conference on Computational Complexity, pages 117-125, 2012. Google Scholar
  4. Ravi B Boppana. The average sensitivity of bounded-depth circuits. Information processing letters, 63(5):257-261, 1997. Google Scholar
  5. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 6-20. ACM, 1986. Google Scholar
  6. Johan Håstad. On the correlation of parity and small-depth circuits. SIAM Journal on Computing, 43(5):1699-1708, 2014. Google Scholar
  7. Russell Impagliazzo, William Matthews, and Ramamohan Paturi. A satisfiability algorithm for AC⁰. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 961-972. SIAM, 2012. Google Scholar
  8. Nathan Keller and Noam Lifshitz. Approximation of biased Boolean functions of small total influence by DNF’s. arXiv preprint, 2017. URL: http://arxiv.org/abs/1703.10116.
  9. Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, Fourier transform, and learnability. Journal of the ACM, 40(3):607-620, 1993. Google Scholar
  10. Alexander A Razborov. An equivalence between second order bounded domain bounded arithmetic and first order bounded arithmetic, 1993. Google Scholar
  11. Benjamin Rossman. An entropy proof of the switching lemma and tight bounds on the decision-tree size of AC⁰ circuits. Google Scholar
  12. Benjamin Rossman. The average sensitivity of bounded-depth formulas. Computational Complexity, 27(2):209-223, 2018. Google Scholar
  13. Benjamin Rossman and Srikanth Srinivasan. Separation of AC⁰[⊕] Formulas and Circuits. In LIPIcs-Leibniz International Proceedings in Informatics, volume 80. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  14. Rahul Santhanam and Ryan Williams. Beating exhaustive search for quantified boolean formulas and connections to circuit complexity. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 231-241. SIAM, 2014. Google Scholar
  15. Dominik Scheder and Li-Yang Tan. On the average sensitivity and density of k-CNF formulas. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 683-698. Springer, 2013. Google Scholar
  16. Avishay Tal. Shrinkage of De Morgan formulae by spectral techniques. In 55th Annual IEEE Symposium on Foundations of Computer Science, pages 551-560, 2014. Google Scholar
  17. Avishay Tal. Tight bounds on the Fourier spectrum of AC⁰. In LIPIcs-Leibniz International Proceedings in Informatics, volume 79. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  18. Patrick Traxler. Variable Influences in Conjunctive Normal Forms. In Theory and Applications of Satisfiability Testing-SAT 2009: 12th International Conference, SAT 2009, Swansea, UK, June 30-July 3, 2009. Proceedings, volume 5584, page 101. Springer, 2009. Google Scholar
  19. Andre M. Zubkov and Aleksandr A. Serov. A complete proof of universal inequalities for the distribution function of the binomial law. Theory of Probability & Its Applications, 57(3):539-544, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail