Document Open Access Logo

The Large-Error Approximate Degree of AC^0

Authors Mark Bun, Justin Thaler

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.55.pdf
  • Filesize: 0.59 MB
  • 16 pages

Document Identifiers

Author Details

Mark Bun
  • Boston University, Boston, MA, USA
Justin Thaler
  • Georgetown University, Washington, DC, USA

Funding

  • Bun, Mark: This work was done while author was at Princeton University and the Simons Institute for the Theory of Computing, supported by a Google Research Fellowship.
  • Thaler, Justin: Supported by NSF Grant CCF-1845125.

Acknowledgements

The authors are grateful to Robin Kothari, Nikhil Mande, Jonathan Ullman, and the anonymous reviewers for valuable comments on earlier versions of this manuscript.

Cite As Get BibTex

Mark Bun and Justin Thaler. The Large-Error Approximate Degree of AC^0. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.55

Abstract

We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight Omega~(n^{1/2}) lower bound on the threshold degree of the SURJECTIVITY function on n variables. This matches the best known threshold degree bound for any AC^0 function, previously exhibited by a much more complicated circuit of larger depth (Sherstov, FOCS 2015). Our result also extends to a 2^{Omega~(n^{1/2})} lower bound on the sign-rank of an AC^0 function, improving on the previous best bound of 2^{Omega(n^{2/5})} (Bun and Thaler, ICALP 2016). 
Second, for any delta>0, we exhibit a function f : {-1,1}^n -> {-1,1} that is computed by a circuit of depth O(1/delta) and is hard to approximate by polynomials in the following sense: f cannot be uniformly approximated to error epsilon=1-2^{-Omega(n^{1-delta})}, even by polynomials of degree n^{1-delta}. Our recent prior work (Bun and Thaler, FOCS 2017) proved a similar lower bound, but which held only for error epsilon=1/3.
Our result implies 2^{Omega(n^{1-delta})} lower bounds on the complexity of AC^0 under a variety of basic measures such as discrepancy, margin complexity, and threshold weight. This nearly matches the trivial upper bound of 2^{O(n)} that holds for every function. The previous best lower bound on AC^0 for these measures was 2^{Omega(n^{1/2})} (Sherstov, FOCS 2015). Additional applications in learning theory, communication complexity, and cryptography are described.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Approximation
  • Theory of computation → Communication complexity
  • Theory of computation → Circuit complexity
Keywords
  • approximate degree
  • discrepancy
  • margin complexity
  • polynomial approximations
  • secret sharing
  • threshold circuits

Metrics

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

Related Versions

References

  1. Eric Allender. A note on the power of threshold circuits. In Foundations of Computer Science, 1989., 30th Annual Symposium on, pages 580-584. IEEE, 1989. Google Scholar
  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: https://doi.org/10.1109/SFCS.1986.15.
  3. Paul Beame and Widad Machmouchi. The quantum query complexity of AC^0. Quantum Information & Computation, 12(7-8):670-676, 2012. URL: http://www.rintonpress.com/xxqic12/qic-12-78/0670-0676.pdf.
  4. Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and Christopher Williamson. Bounded Indistinguishability and the Complexity of Recovering Secrets. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part III, volume 9816 of Lecture Notes in Computer Science, pages 593-618. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53015-3_21.
  5. Andrej Bogdanov and Christopher Williamson. Approximate Bounded Indistinguishability. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 53:1-53:11, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.53.
  6. Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan. On The Power of Statistical Zero Knowledge. In To Appear In Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS), 2017. Preliminary version available at URL: http://eccc.hpi-web.de/report/2016/140.
  7. 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: https://doi.org/10.1109/CCC.2007.18.
  8. Mark Bun, Robin Kothari, and Justin Thaler. The polynomial method strikes back: Tight quantum query bounds via dual polynomials. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 297-310. ACM, 2018. Google Scholar
  9. 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: https://doi.org/10.1007/978-3-642-39206-1_26.
  10. 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 151. URL: https://doi.org/10.1007/978-3-662-47672-7_22.
  11. Mark Bun and Justin Thaler. Approximate Degree and the Complexity of Depth Three Circuits. Electronic Colloquium on Computational Complexity (ECCC), 23:121, 2016. URL: http://eccc.hpi-web.de/report/2016/121.
  12. Mark Bun and Justin Thaler. Improved Bounds on the Sign-Rank of AC⁰. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 37:1-37:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.37.
  13. 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: https://doi.org/10.1109/FOCS.2017.10.
  14. Kuan Cheng, Yuval Ishai, and Xin Li. Near-Optimal Secret Sharing and Error Correcting Codes in AC⁰. In Theory of Cryptography Conference, pages 424-458. Springer, 2017. Google Scholar
  15. Vitaly Feldman. Evolvability from learning algorithms. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 619-628. ACM, 2008. Google Scholar
  16. Jürgen Forster. A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pages 100-106. IEEE Computer Society, 2001. URL: https://doi.org/10.1109/CCC.2001.933877.
  17. Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, and Hans Ulrich Simon. Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity. In Ramesh Hariharan, Madhavan Mukund, and V. Vinay, editors, FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 21st Conference, Bangalore, India, December 13-15, 2001, Proceedings, volume 2245 of Lecture Notes in Computer Science, pages 171-182. Springer, 2001. URL: https://doi.org/10.1007/3-540-45294-X_15.
  18. Hartmut Klauck. Lower bounds for quantum communication complexity. In Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, pages 288-297. IEEE, 2001. Google Scholar
  19. 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: https://doi.org/10.1016/j.jcss.2003.07.007.
  20. 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: https://doi.org/10.1016/S0304-3975(96)00019-9.
  21. Troy Lee. A note on the sign degree of formulas. CoRR, abs/0909.4607, 2009. URL: http://arxiv.org/abs/0909.4607.
  22. Nati Linial and Adi Shraibman. Learning complexity vs communication complexity. Combinatorics, Probability and Computing, 18(1-2):227-245, 2009. Google Scholar
  23. Marvin Minsky and Seymour Papert. Perceptrons - an introduction to computational geometry. MIT Press, 1969. Google Scholar
  24. Noam Nisan. The Communication Complexity of Threshold Gates. In Combinatorics, Paul Erdos is Eighty, pages 301-315, 1994. Google Scholar
  25. Ryan O'Donnell and Rocco A. Servedio. New degree bounds for polynomial threshold functions. Combinatorica, 30(3):327-358, 2010. Preliminary version in STOC 2003. URL: https://doi.org/10.1007/s00493-010-2173-3.
  26. Ramamohan Paturi and Janos Simon. Probabilistic Communication Complexity. J. Comput. Syst. Sci., 33(1):106-123, 1986. URL: https://doi.org/10.1016/0022-0000(86)90046-2.
  27. Vladimir V Podolskii. Perceptrons of large weight. In International Computer Science Symposium in Russia, pages 328-336. Springer, 2007. Google Scholar
  28. Alexander A. Razborov and Alexander A. Sherstov. The Sign-Rank of AC⁰. SIAM J. Comput., 39(5):1833-1855, 2010. URL: https://doi.org/10.1137/080744037.
  29. Alexander A. Sherstov. Separating AC^0 from Depth-2 Majority Circuits. SIAM J. Comput., 38(6):2113-2129, 2009. URL: https://doi.org/10.1137/08071421X.
  30. Alexander A. Sherstov. Strong direct product theorems for quantum communication and query complexity. In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 41-50. ACM, 2011. URL: https://doi.org/10.1145/1993636.1993643.
  31. Alexander A. Sherstov. The Pattern Matrix Method. SIAM J. Comput., 40(6):1969-2000, 2011. Preliminary version in STOC 2008. URL: https://doi.org/10.1137/080733644.
  32. Alexander A. Sherstov. The Intersection of Two Halfspaces Has High Threshold Degree. SIAM J. Comput., 42(6):2329-2374, 2013. Preliminary version in FOCS 2009. URL: https://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: https://doi.org/10.1145/2591796.2591871.
  34. Alexander A. Sherstov. The Power of Asymmetry in Constant-Depth Circuits. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 431-450, 2015. URL: https://doi.org/10.1109/FOCS.2015.34.
  35. Alexander A. Sherstov. Algorithmic polynomials. Electronic Colloquium on Computational Complexity (ECCC), 25:10, 2018. To appear in STOC 2018. URL: https://eccc.weizmann.ac.il/report/2018/010.
  36. Alexander A. Sherstov and Pei Wu. Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0. Electronic Colloquium on Computational Complexity (ECCC), 26:3, 2019. URL: https://eccc.weizmann.ac.il/report/2019/003.
  37. Yaoyun Shi and Yufan Zhu. Quantum communication complexity of block-composed functions. Quantum Information & Computation, 9(5):444-460, 2009. URL: http://www.rintonpress.com/xxqic9/qic-9-56/0444-0460.pdf.
  38. Leslie G Valiant. Evolvability. Journal of the ACM (JACM), 56(1):3, 2009. 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