Document Open Access Logo

Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract)

Authors Yuval Filmus , Or Meir , Avishay Tal

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.89.pdf
  • Filesize: 424 kB
  • 7 pages

Document Identifiers

Author Details

Yuval Filmus
  • Technion - Israel Institute of Technology, Haifa, Israel
Or Meir
  • Department of Computer Science, University of Haifa, Israel
Avishay Tal
  • Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, CA, USA

Funding

  • Filmus, Yuval: Taub Fellow - supported by the Taub Foundations. The research was funded by ISF grant 1337/16.
  • Meir, Or: Partially supported by the Israel Science Foundation (grant No. 1445/16).

Acknowledgements

A.T. would like to thank Igor Carboni Oliveira for bringing the question of proving formula size lower bounds for AC⁰ to his attention. We are also grateful to Robin Kothari for posing this open question on "Theoretical Computer Science Stack Exchange" [Kothari, 2011], and to Kaveh Ghasemloo and Stasys Jukna for their feedback on this question. We would like to thank Anna Gál for very helpful discussions.

Cite As Get BibTex

Yuval Filmus, Or Meir, and Avishay Tal. Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 89:1-89:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITCS.2021.89

Abstract

Håstad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of O(p²) under a random restriction that leaves each variable alive independently with probability p [SICOMP, 1998]. Using this result, he gave an Ω̃(n³) formula size lower bound for the Andreev function, which, up to lower order improvements, remains the state-of-the-art lower bound for any explicit function. 
In this work, we extend the shrinkage result of Håstad to hold under a far wider family of random restrictions and their generalization - random projections. Based on our shrinkage results, we obtain an Ω̃(n³) formula size lower bound for an explicit function computed in AC⁰. This improves upon the best known formula size lower bounds for AC⁰, that were only quadratic prior to our work. In addition, we prove that the KRW conjecture [Karchmer et al., Computational Complexity 5(3/4), 1995] holds for inner functions for which the unweighted quantum adversary bound is tight. In particular, this holds for inner functions with a tight Khrapchenko bound.
Our random projections are tailor-made to the function’s structure so that the function maintains structure even under projection - using such projections is necessary, as standard random restrictions simplify AC⁰ circuits. In contrast, we show that any De Morgan formula shrinks by a quadratic factor under our random projections, allowing us to prove the cubic lower bound.
Our proof techniques build on the proof of Håstad for the simpler case of balanced formulas. This allows for a significantly simpler proof at the cost of slightly worse parameters. As such, when specialized to the case of p-random restrictions, our proof can be used as an exposition of Håstad’s result.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • De Morgan formulas
  • KRW Conjecture
  • shrinkage
  • random restrictions
  • random projections
  • bounded depth circuits
  • constant depth circuits
  • formula complexity

Metrics

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

Related Versions

References

  1. Miklós Ajtai. Σ₁¹-formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1-48, 1983. Google Scholar
  2. Andris Ambainis. Quantum lower bounds by quantum arguments. J. Comput. System Sci., 64(4):750-767, 2002. Special issue on STOC 2000 (Portland, OR). URL: https://doi.org/10.1006/jcss.2002.1826.
  3. Alexander E. Andreev. On a method for obtaining more than quadratic effective lower bounds for the complexity of π-schemes. Moscow University Mathematics Bulletin, 42(1):24-29, 1987. Google Scholar
  4. Paul Beame and Widad Machmouchi. The quantum query complexity of AC0. Quantum Info. Comput., 12(7-8):670-676, July 2012. Google Scholar
  5. Andrew M. Childs, Shelby Kimmel, and Robin Kothari. The quantum query complexity of read-many formulas. In Leah Epstein and Paolo Ferragina, editors, Algorithms - ESA 2012, pages 337-348, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  6. Irit Dinur and Or Meir. Toward the KRW composition conjecture: Cubic formula lower bounds via communication complexity. Computational Complexity, 27(3):375-462, 2018. Google Scholar
  7. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. Google Scholar
  8. Anna Gál, Avishay Tal, and Adrian Trejo Nuñez. Cubic formula size lower bounds based on compositions with majority. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 35:1-35:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.35.
  9. Dmitry Gavinsky, Or Meir, Omri Weinstein, and Avi Wigderson. Toward better formula lower bounds: The composition of a function and a universal relation. SIAM J. Comput., 46(1):114-131, 2017. Google Scholar
  10. Mikael Goldmann and Johan Håstad. A simple lower bound for monotone clique using a communication game. Inf. Process. Lett., 41(4):221-226, 1992. Google Scholar
  11. Mika Göös and Toniann Pitassi. Communication lower bounds via critical block sensitivity. SIAM J. Comput., 47(5):1778-1806, 2018. Google Scholar
  12. Johan Håstad. Almost optimal lower bounds for small depth circuits. In STOC, pages 6-20, 1986. Google Scholar
  13. Johan Håstad. The shrinkage exponent is 2. In Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, SFCS '93, pages 114-123, USA, 1993. IEEE Computer Society. URL: https://doi.org/10.1109/SFCS.1993.366876.
  14. Johan Håstad. The shrinkage exponent of de Morgan formulas is 2. SIAM J. Comput., 27(1):48-64, 1998. Google Scholar
  15. Johan Håstad, Stasys Jukna, and Pavel Pudlák. Top-down lower bounds for depth-three circuits. Computational Complexity, 5(2):99-112, 1995. Google Scholar
  16. Johan Håstad, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan. An average-case depth hierarchy theorem for boolean circuits. J. ACM, 64(5):35:1-35:27, 2017. URL: https://doi.org/10.1145/3095799.
  17. Johan Torkel Håstad. Computational limitations for small-depth circuits. MIT press, 1987. Google Scholar
  18. Russell Impagliazzo and Noam Nisan. The effect of random restrictions on formula size. Random Struct. Algorithms, 4(2):121-134, 1993. Google Scholar
  19. Stasys Jukna. Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and combinatorics. Springer, 2012. Google Scholar
  20. Mauricio Karchmer, Ran Raz, and Avi Wigderson. Super-logarithmic depth lower bounds via the direct sum in communication complexity. Computational Complexity, 5(3/4):191-204, 1995. Google Scholar
  21. Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math., 3(2):255-265, 1990. Google Scholar
  22. V. M. Khrapchenko. A method of obtaining lower bounds for the complexity of π-schemes. Mathematical Notes Academy of Sciences USSR, 10:474-479, 1972. Google Scholar
  23. Robin Kothari. Formula size lower bounds for AC0 functions, 2011. Question on Theoretical Computer Science Stack Exchange. URL: https://cstheory.stackexchange.com/questions/7156/formula-size-lower-bounds-for-ac0-functions.
  24. E. I. Neciporuk. On a Boolean function. Soviet Mathematics Doklady, 7(4):999-1000, 1966. Google Scholar
  25. Mike Paterson and Uri Zwick. Shrinkage of de Morgan formulae under restriction. Random Struct. Algorithms, 4(2):135-150, 1993. Google Scholar
  26. Toniann Pitassi and Robert Robere. Strongly exponential lower bounds for monotone computation. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1246-1255, 2017. Google Scholar
  27. Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. Combinatorica, 19(3):403-435, 1999. Google Scholar
  28. Ran Raz and Avi Wigderson. Monotone circuits for matching require linear depth. J. ACM, 39(3):736-744, 1992. Google Scholar
  29. Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan. An average-case depth hierarchy theorem for Boolean circuits. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1030-1048, 2015. Google Scholar
  30. Bella Abramovna Subbotovskaya. Realizations of linear functions by formulas using +,.,-. Soviet Mathematics Doklady, 2:110-112, 1961. Google Scholar
  31. Avishay Tal. Shrinkage of de Morgan formulae by spectral techniques. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 551-560, 2014. Google Scholar
  32. Andrew Chi-Chih Yao. Separating the polynomial-time hierarchy by oracles (preliminary version). In FOCS, pages 1-10. IEEE Computer Society, 1985. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact