Approximate Degree and the Complexity of Depth Three Circuits

Authors Mark Bun, Justin Thaler



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.35.pdf
  • Filesize: 0.6 MB
  • 18 pages

Document Identifiers

Author Details

Mark Bun
  • Princeton University, Princeton, NJ, USA
Justin Thaler
  • Georgetown University, Washington, DC, USA

Cite AsGet BibTex

Mark Bun and Justin Thaler. Approximate Degree and the Complexity of Depth Three Circuits. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.35

Abstract

Threshold weight, margin complexity, and Majority-of-Threshold circuit size are basic complexity measures of Boolean functions that arise in learning theory, communication complexity, and circuit complexity. Each of these measures might exhibit a chasm at depth three: namely, all polynomial size Boolean circuits of depth two have polynomial complexity under the measure, but there may exist Boolean circuits of depth three that have essentially maximal complexity exp(Theta(n)). However, existing techniques are far from showing this: for all three measures, the best lower bound for depth three circuits is exp(Omega(n^{2/5})). Moreover, prior methods exclusively study block-composed functions. Such methods appear intrinsically unable to prove lower bounds better than exp(Omega(sqrt{n})) even for depth four circuits, and have yet to prove lower bounds better than exp(Omega(sqrt{n})) for circuits of any constant depth. We take a step toward showing that all of these complexity measures indeed exhibit a chasm at depth three. Specifically, for any arbitrarily small constant delta > 0, we exhibit a depth three circuit of polynomial size (in fact, an O(log n)-decision list) of complexity exp(Omega(n^{1/2-delta})) under each of these measures. Our methods go beyond the block-composed functions studied in prior work, and hence may not be subject to the same barriers. Accordingly, we suggest natural candidate functions that may exhibit stronger bounds.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • approximate degree
  • communication complexity
  • learning theory
  • polynomial approximation
  • threshold circuits

Metrics

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

References

  1. Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. J. ACM, 51(4):595-605, 2004. URL: http://dx.doi.org/10.1145/1008731.1008735.
  2. László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory (preliminary version). In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages 337-347. IEEE Computer Society, 1986. URL: http://dx.doi.org/10.1109/SFCS.1986.15.
  3. Richard Beigel. Perceptrons, PP, and the Polynomial Hierarchy. Computational Complexity, 4:339-349, 1994. URL: http://dx.doi.org/10.1007/BF01263422.
  4. Richard Beigel, Nick Reingold, and Daniel A. Spielman. PP is closed under intersection. J. Comput. Syst. Sci., 50(2):191-202, 1995. URL: http://dx.doi.org/10.1006/jcss.1995.1017.
  5. Harry Buhrman, Nikolai K. Vereshchagin, and Ronald de Wolf. On computation and communication with small bias. In 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 13-16 June 2007, San Diego, California, USA, pages 24-32. IEEE Computer Society, 2007. URL: http://dx.doi.org/10.1109/CCC.2007.18.
  6. Mark Bun, Robin Kothari, and Justin Thaler. The polynomial method strikes back: Tight quantum query bounds via dual polynomials. In Symposium on Theory of Computing (STOC), pages 297-310. ACM, 2018. URL: http://dx.doi.org/10.1145/3188745.3188784.
  7. Mark Bun and Justin Thaler. Dual lower bounds for approximate degree and markov-bernstein inequalities. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, ICALP (1), volume 7965 of Lecture Notes in Computer Science, pages 303-314. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_26.
  8. Mark Bun and Justin Thaler. Hardness amplification and the approximate degree of constant-depth circuits. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 268-280. Springer, 2015. Full version available at http://eccc.hpi-web.de/report/2013/151. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_22.
  9. Mark Bun and Justin Thaler. A nearly optimal lower bound on the approximate degree of AC^0. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 1-12, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.10.
  10. Mikael Goldmann, Johan Håstad, and Alexander A. Razborov. Majority gates VS. general weighted threshold gates. Computational Complexity, 2:277-300, 1992. URL: http://dx.doi.org/10.1007/BF01200426.
  11. Mika Göös, Toniann Pitassi, and Thomas Watson. The landscape of communication complexity classes. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 86:1-86:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.86.
  12. András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, and György Turán. Threshold circuits of bounded depth. J. Comput. Syst. Sci., 46(2):129-154, 1993. URL: http://dx.doi.org/10.1016/0022-0000(93)90001-D.
  13. Hartmut Klauck. Lower bounds for quantum communication complexity. SIAM J. Comput., 37(1):20-46, 2007. URL: http://dx.doi.org/10.1137/S0097539702405620.
  14. Adam R. Klivans and Rocco A. Servedio. Learning DNF in time 2^Õ(n^1/3). J. Comput. Syst. Sci., 68(2):303-318, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2003.07.007.
  15. Adam R. Klivans and Rocco A. Servedio. Toward attribute efficient learning of decision lists and parities. Journal of Machine Learning Research, 7:587-602, 2006. URL: http://www.jmlr.org/papers/v7/klivans06a.html.
  16. Matthias Krause. On the computational power of boolean decision lists. Computational Complexity, 14(4):362-375, 2006. URL: http://dx.doi.org/10.1007/s00037-005-0203-0.
  17. Matthias Krause and Pavel Pudlák. On the computational power of depth-2 circuits with threshold and modulo gates. Theor. Comput. Sci., 174(1-2):137-156, 1997. URL: http://dx.doi.org/10.1016/S0304-3975(96)00019-9.
  18. Matthias Krause and Pavel Pudlák. Computing boolean functions by polynomials and threshold circuits. Computational Complexity, 7(4):346-370, 1998. URL: http://dx.doi.org/10.1007/s000370050015.
  19. Troy Lee. A note on the sign degree of formulas. arXiv, abs/0909.4607, 2009. URL: http://arxiv.org/abs/0909.4607.
  20. Nati Linial and Adi Shraibman. Learning complexity vs. communication complexity. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pages 53-63. IEEE Computer Society, 2008. URL: http://dx.doi.org/10.1109/CCC.2008.28.
  21. Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2(4):285-318, 1987. URL: http://dx.doi.org/10.1007/BF00116827.
  22. Marvin Minsky and Seymour Papert. Perceptrons - an introduction to computational geometry. MIT Press, 1969. Google Scholar
  23. Noam Nisan. The communication complexity of threshold gates. In Combinatorics, Paul Erdos is Eighty, pages 301-315, 1994. Google Scholar
  24. Vladimir V. Podolskii. A uniform lower bound on weights of perceptrons. In Edward A. Hirsch, Alexander A. Razborov, Alexei L. Semenov, and Anatol Slissenko, editors, Computer Science - Theory and Applications, Third International Computer Science Symposium in Russia, CSR 2008, Moscow, Russia, June 7-12, 2008, Proceedings, volume 5010 of Lecture Notes in Computer Science, pages 261-272. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-79709-8_27.
  25. Vladimir Vladimirovich Podolskii. Perceptrons of large weight. Problems of Information Transmission, 45(1):46-53, 2009. Google Scholar
  26. Ronald L. Rivest. Learning decision lists. Machine Learning, 2(3):229-246, 1987. URL: http://dx.doi.org/10.1007/BF00058680.
  27. Rocco A. Servedio, Li-Yang Tan, and Justin Thaler. Attribute-efficient learning and weight-degree tradeoffs for polynomial threshold functions. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, COLT, volume 23 of JMLR Proceedings, pages 14.1-14.19. JMLR.org, 2012. URL: http://www.jmlr.org/proceedings/papers/v23/servedio12/servedio12.pdf.
  28. A. A. Sherstov. The power of asymmetry in constant-depth circuits. In FOCS, 2015. Full version available at URL: http://eccc.hpi-web.de/report/2015/147/.
  29. Alexander A. Sherstov. Separating AC^0 from depth-2 majority circuits. SIAM J. Comput., 38(6):2113-2129, 2009. URL: http://dx.doi.org/10.1137/08071421X.
  30. Alexander A. Sherstov. The pattern matrix method. SIAM J. Comput., 40(6):1969-2000, 2011. URL: http://dx.doi.org/10.1137/080733644.
  31. Alexander A. Sherstov. Approximating the and-or tree. Theory of Computing, 9(20):653-663, 2013. Google Scholar
  32. Alexander A. Sherstov. The intersection of two halfspaces has high threshold degree. SIAM J. Comput., 42(6):2329-2374, 2013. URL: http://dx.doi.org/10.1137/100785260.
  33. Alexander A. Sherstov. Breaking the Minsky-Papert barrier for constant-depth circuits. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 223-232. ACM, 2014. URL: http://dx.doi.org/10.1145/2591796.2591871.
  34. Justin Thaler. Lower bounds for the approximate degree of block-composed functions. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 17:1-17:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.17.
  35. Leslie G. Valiant. A theory of the learnable. In Richard A. DeMillo, editor, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA, pages 436-445. ACM, 1984. URL: http://dx.doi.org/10.1145/800057.808710.
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