Document Open Access Logo

Shrinkage of Decision Lists and DNF Formulas

Author Benjamin Rossman

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2021.70.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • shrinkage
  • decision lists
  • DNF formulas

Metrics

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

Abstract

We establish nearly tight bounds on the expected shrinkage of decision lists and DNF formulas under the p-random restriction R_p for all values of p ∈ [0,1]. For a function f with domain {0,1}ⁿ, let DL(f) denote the minimum size of a decision list that computes f. We show that E[DL(f ↾ R_p)] ≤ DL(f)^log_{2/(1-p)}((1+p)/(1-p)). For example, this bound is √{DL(f)} when p = √5-2 ≈ 0.24. For Boolean functions f, we obtain the same shrinkage bound with respect to DNF formula size plus 1 (i.e., replacing DL(⋅) with DNF(⋅)+1 on both sides of the inequality).

Cite As Get BibTex

Benjamin Rossman. Shrinkage of Decision Lists and DNF Formulas. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITCS.2021.70

Author Details

Benjamin Rossman
  • Duke University, Durham, NC, USA

Acknowledgements

I am grateful to the anonymous referees of ITCS 2021 for their valuable comments and to the authors of [Lovett et al., 2020], Shachar Lovett, Kewen Wu and Jiapeng Zhang, for stimulating conversations related to this work.

References

  1. Alexander E Andreev. On a method for obtaining more than quadratic effective lower bounds for the complexity of π-schemes. Moscow Univ. Math. Bull., 42(1):63-66, 1987. 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. Avrim Blum. Rank-r decision trees are a subclass of r-decision lists. Information Processing Letters, 42(4):183-185, 1992. Google Scholar
  4. Nader H Bshouty. A subexponential exact learning algorithm for dnf using equivalence queries. Information Processing Letters, 59(1):37-39, 1996. Google Scholar
  5. Moshe Dubiner and Uri Zwick. How do read-once formulae shrink? parity, 2(1):63, 1993. Google Scholar
  6. Yuval Filmus, Or Meir, and Avishay Tal. Shrinkage under random projections and cubic formula lower bounds for AC⁰. In 12th Innovations in Theoretical Computer Science Conference (ITCS), 2021. Google Scholar
  7. Parikshit Gopalan, Raghu Meka, and Omer Reingold. DNF sparsification and a faster deterministic counting algorithm. Computational Complexity, 22(2):275-310, 2013. Google Scholar
  8. Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan. Better pseudorandom generators from milder pseudorandom restrictions. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 120-129. IEEE, 2012. Google Scholar
  9. Thomas Hancock, Tao Jiang, Ming Li, and John Tromp. Lower bounds on learning decision lists and trees. Information and Computation, 126(2):114-122, 1996. Google Scholar
  10. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Proc. 18th ACM Symposium on Theory of Computing, pages 6-20, 1986. Google Scholar
  11. Johan Håstad. The shrinkage exponent of de Morgan formulas is 2. SIAM Journal on Computing, 27(1):48-64, 1998. Google Scholar
  12. Johan Håstad. On the correlation of parity and small-depth circuits. SIAM Journal on Computing, 43(5):1699-1708, 2014. Google Scholar
  13. Johan Håstad, Alexander Razborov, and Andrew Yao. On the shrinkage exponent for read-once formulae. Theoretical Computer Science, 141(1-2):269-282, 1995. Google Scholar
  14. Russell Impagliazzo and Noam Nisan. The effect of random restrictions on formula size. Random Structures & Algorithms, 4(2):121-133, 1993. Google Scholar
  15. Ilan Komargodski and Ran Raz. Average-case lower bounds for formula size. In Proceedings of the 45th ACM Symposium on Theory of Computing, pages 171-180, 2013. Google Scholar
  16. Matthias Krause. On the computational power of boolean decision lists. Computational Complexity, 14(4):362-375, 2006. Google Scholar
  17. Shachar Lovett, Kewen Wu, and Jiapeng Zhang. Decision list compression by mild random restrictions. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 247-254, 2020. Google Scholar
  18. Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014. Google Scholar
  19. Michael S Paterson and Uri Zwick. Shrinkage of de Morgan formulae under restriction. Random Structures & Algorithms, 4(2):135-150, 1993. Google Scholar
  20. Alexander A Razborov. Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution. Annals of Mathematics, pages 415-472, 2015. Google Scholar
  21. Ronald L Rivest. Learning decision lists. Machine learning, 2(3):229-246, 1987. Google Scholar
  22. Benjamin Rossman. Criticality of Regular Formulas. In 34th Computational Complexity Conference (CCC 2019), volume 137 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1-28, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.1.
  23. Rahul Santhanam. Fighting perebor: New and improved algorithms for formula and QBF satisfiability. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 183-192. IEEE, 2010. Google Scholar
  24. Nathan Segerlind, Sam Buss, and Russell Impagliazzo. A switching lemma for small restrictions and lower bounds for k-DNF resolution. SIAM Journal on Computing, 33(5):1171-1200, 2004. Google Scholar
  25. Bella A. Subbotovskaya. Realizations of linear functions by formulas using +,⋅,-. Doklady Akademii Nauk SSSR, 136(3):553-555, 1961. Google Scholar
  26. 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
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
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact