Document Open Access Logo

Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity

Authors Lijie Chen, R. Ryan Williams

PDF
Thumbnail PDF

File

LIPIcs.CCC.2019.19.pdf
  • Filesize: 0.83 MB
  • 43 pages

Document Identifiers

Author Details

Lijie Chen
  • MIT, Cambridge, MA, USA
R. Ryan Williams
  • MIT, Cambridge, MA, USA

Funding

Supported by NSF CCF-1741615 (Common Links in Algorithms and Complexity) and a Google Faculty Research Award.

Acknowledgements

Part of this work was completed while the authors were visiting the Simons Institute at UC Berkeley, as part of the program on Lower Bounds in Computational Complexity. We thank them for their hospitality and excellent environment. We also thank Josh Alman for helpful last-minute proofreading, and the CCC reviewers for useful comments.

Cite AsGet BibTex

Lijie Chen and R. Ryan Williams. Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 19:1-19:43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.CCC.2019.19

Abstract

We considerably sharpen the known connections between circuit-analysis algorithms and circuit lower bounds, show intriguing equivalences between the analysis of weak circuits and (apparently difficult) circuits, and provide strong new lower bounds for approximately computing Boolean functions with depth-two neural networks and related models. - We develop approaches to proving THR o THR lower bounds (a notorious open problem), by connecting algorithmic analysis of THR o THR to the provably weaker circuit classes THR o MAJ and MAJ o MAJ, where exponential lower bounds have long been known. More precisely, we show equivalences between algorithmic analysis of THR o THR and these weaker classes. The epsilon-error CAPP problem asks to approximate the acceptance probability of a given circuit to within additive error epsilon; it is the "canonical" derandomization problem. We show: - There is a non-trivial (2^n/n^{omega(1)} time) 1/poly(n)-error CAPP algorithm for poly(n)-size THR o THR circuits if and only if there is such an algorithm for poly(n)-size MAJ o MAJ. - There is a delta > 0 and a non-trivial SAT (delta-error CAPP) algorithm for poly(n)-size THR o THR circuits if and only if there is such an algorithm for poly(n)-size THR o MAJ. Similar results hold for depth-d linear threshold circuits and depth-d MAJORITY circuits. These equivalences are proved via new simulations of THR circuits by circuits with MAJ gates. - We strengthen the connection between non-trivial derandomization (non-trivial CAPP algorithms) for a circuit class C, and circuit lower bounds against C. Previously, [Ben-Sasson and Viola, ICALP 2014] (following [Williams, STOC 2010]) showed that for any polynomial-size class C closed under projections, non-trivial (2^{n}/n^{omega(1)} time) CAPP for OR_{poly(n)} o AND_{3} o C yields NEXP does not have C circuits. We apply Probabilistic Checkable Proofs of Proximity in a new way to show it would suffice to have a non-trivial CAPP algorithm for either XOR_2 o C, AND_2 o C or OR_2 o C. - A direct corollary of the first two bullets is that NEXP does not have THR o THR circuits would follow from either: - a non-trivial delta-error CAPP (or SAT) algorithm for poly(n)-size THR o MAJ circuits, or - a non-trivial 1/poly(n)-error CAPP algorithm for poly(n)-size MAJ o MAJ circuits. - Applying the above machinery, we extend lower bounds for depth-two neural networks and related models [R. Williams, CCC 2018] to weak approximate computations of Boolean functions. For example, for arbitrarily small epsilon > 0, we prove there are Boolean functions f computable in nondeterministic n^{log n} time such that (for infinitely many n) every polynomial-size depth-two neural network N on n inputs (with sign or ReLU activation) must satisfy max_{x in {0,1}^n}|N(x)-f(x)|>1/2-epsilon. That is, short linear combinations of ReLU gates fail miserably at computing f to within close precision. Similar results are proved for linear combinations of ACC o THR circuits, and linear combinations of low-degree F_p polynomials. These results constitute further progress towards THR o THR lower bounds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • PCP of Proximity
  • Circuit Lower Bounds
  • Derandomization
  • Threshold Circuits
  • ReLU

Metrics

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

References

  1. Amir Abboud and Karl Bringmann. Tighter Connections Between Formula-SAT and Shaving Logs. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 8:1-8:18, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.8.
  2. Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. ACM, 57(3):14:1-14:36, 2010. URL: https://doi.org/10.1145/1706591.1706594.
  3. Josh Alman, Timothy M. Chan, and R. Ryan Williams. Polynomial Representations of Threshold Functions and Algorithmic Applications. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 467-476, 2016. URL: https://doi.org/10.1109/FOCS.2016.57.
  4. Kazuyuki Amano and Akira Maruoka. On the Complexity of Depth-2 Circuits with Threshold Gates. In Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29 - September 2, 2005, Proceedings, pages 107-118, 2005. URL: https://doi.org/10.1007/11549345_11.
  5. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof Verification and the Hardness of Approximation Problems. J. ACM, 45(3):501-555, 1998. URL: https://doi.org/10.1145/278298.278306.
  6. Sanjeev Arora and Shmuel Safra. Probabilistic Checking of Proofs: A New Characterization of NP. J. ACM, 45(1):70-122, 1998. URL: https://doi.org/10.1145/273865.273901.
  7. László Babai, Kristoffer Arnsfelt Hansen, Vladimir V Podolskii, and Xiaoming Sun. Weights of exact threshold functions. In International Symposium on Mathematical Foundations of Computer Science, pages 66-77. Springer, 2010. Google Scholar
  8. Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, and Srikanth Srinivasan. A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, pages 8:1-8:20, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.8.
  9. Paul Beame, Stephen A. Cook, and H. James Hoover. Log Depth Circuits for Division and Related Problems. SIAM J. Comput., 15(4):994-1003, 1986. URL: https://doi.org/10.1137/0215070.
  10. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Short PCPs Verifiable in Polylogarithmic Time. In 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 11-15 June 2005, San Jose, CA, USA, pages 120-134, 2005. URL: https://doi.org/10.1109/CCC.2005.27.
  11. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM J. Comput., 36(4):889-974, 2006. URL: https://doi.org/10.1137/S0097539705446810.
  12. Eli Ben-Sasson and Emanuele Viola. Short PCPs with Projection Queries. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 163-173, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_14.
  13. Eli Ben-Sasson and Emanuele Viola. Short PCPs with projection queries. In International Colloquium on Automata, Languages, and Programming, pages 163-173. Springer, 2014. Google Scholar
  14. 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, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 297-310, 2018. URL: https://doi.org/10.1145/3188745.3188784.
  15. 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.
  16. Arkadev Chattopadhyay and Nikhil S. Mande. A Short List of Equalities Induces Large Sign Rank. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 47-58, 2018. URL: https://doi.org/10.1109/FOCS.2018.00014.
  17. Ruiwen Chen and Rahul Santhanam. Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP. In Theory and Applications of Satisfiability Testing - SAT 2015 - 18th International Conference, Austin, TX, USA, September 24-27, 2015, Proceedings, pages 33-45, 2015. URL: https://doi.org/10.1007/978-3-319-24318-4_4.
  18. Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. URL: https://doi.org/10.1145/1236457.1236459.
  19. 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 FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 21st Conference, Bangalore, India, December 13-15, 2001, Proceedings, pages 171-182, 2001. URL: https://doi.org/10.1007/3-540-45294-X_15.
  20. M. R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci., 1(3):237-267, 1976. URL: https://doi.org/10.1016/0304-3975(76)90059-1.
  21. Mikael Goldmann, Johan Håstad, and Alexander A. Razborov. Majority Gates VS. General Weighted Threshold Gates. Computational Complexity, 2:277-300, 1992. URL: https://doi.org/10.1007/BF01200426.
  22. Hans Dietmar Groeger and György Turán. A linear lower bound for the size of threshold circuits. Bulletin-European Association For Theoretical Computer Science, 50:220-220, 1993. Google Scholar
  23. 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: https://doi.org/10.1016/0022-0000(93)90001-D.
  24. Kristoffer Arnsfelt Hansen and Vladimir V. Podolskii. Exact Threshold Circuits. In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, June 9-12, 2010, pages 270-279, 2010. URL: https://doi.org/10.1109/CCC.2010.33.
  25. Kristoffer Arnsfelt Hansen and Vladimir V. Podolskii. Polynomial threshold functions and Boolean threshold circuits. Inf. Comput., 240:56-73, 2015. URL: https://doi.org/10.1016/j.ic.2014.09.008.
  26. William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci., 65(4):695-716, 2002. URL: https://doi.org/10.1016/S0022-0000(02)00025-9.
  27. Thomas Hofmeister. A Note on the Simulation of Exponential Threshold Weights. In Computing and Combinatorics, Second Annual International Conference, COCOON '96, Hong Kong, June 17-19, 1996, Proceedings, pages 136-141, 1996. URL: https://doi.org/10.1007/3-540-61332-3_146.
  28. Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks. Size-Depth Tradeoffs for Threshold Circuits. SIAM J. Comput., 26(3):693-707, 1997. URL: https://doi.org/10.1137/S0097539792282965.
  29. Russell Impagliazzo, Ramamohan Paturi, and Stefan Schneider. A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 479-488, 2013. URL: https://doi.org/10.1109/FOCS.2013.58.
  30. Hamid Jahanjou, Eric Miles, and Emanuele Viola. Local Reductions. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 749-760, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_61.
  31. Daniel M. Kane and Ryan Williams. Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 633-643, 2016. URL: https://doi.org/10.1145/2897518.2897636.
  32. Wolfgang Maass. Bounds for the Computational Power and Learning Complexity of Analog Neural Nets. SIAM J. Comput., 26(3):708-732, 1997. URL: https://doi.org/10.1137/S0097539793256041.
  33. Saburo Muroga, Iwao Toda, and Satoru Takasu. Theory of majority decision elements. Journal of the Franklin Institute, 271(5):376-418, 1961. Google Scholar
  34. Cody Murray and R. Ryan Williams. Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 890-901, 2018. URL: https://doi.org/10.1145/3188745.3188910.
  35. Noam Nisan. The communication complexity of threshold gates. Combinatorics, Paul Erdos is Eighty, 1:301-315, 1993. Google Scholar
  36. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. URL: http://www.cambridge.org/de/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/analysis-boolean-functions.
  37. Ramamohan Paturi and Michael E. Saks. Approximating Threshold Circuits by Rational Functions. Inf. Comput., 112(2):257-272, 1994. URL: https://doi.org/10.1006/inco.1994.1059.
  38. John H. Reif and Stephen R. Tate. On Threshold Circuits and Polynomial Computation. SIAM J. Comput., 21(5):896-908, 1992. URL: https://doi.org/10.1137/0221053.
  39. Theodore J Rivlin. An introduction to the approximation of functions. Courier Corporation, 2003. Google Scholar
  40. Vwani P. Roychowdhury, Alon Orlitsky, and Kai-Yeung Siu. Lower bounds on threshold and related circuits via communication complexity. IEEE Trans. Information Theory, 40(2):467-474, 1994. URL: https://doi.org/10.1109/18.312169.
  41. Rahul Santhanam and Ryan Williams. On Medium-Uniformity and Circuit Lower Bounds. In Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013, pages 15-23, 2013. URL: https://doi.org/10.1109/CCC.2013.40.
  42. Alexander A. Sherstov. Algorithmic polynomials. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 311-324, 2018. URL: https://doi.org/10.1145/3188745.3188958.
  43. Daniel A. Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Trans. Information Theory, 42(6):1723-1731, 1996. URL: https://doi.org/10.1109/18.556668.
  44. Suguru Tamaki. A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates. Electronic Colloquium on Computational Complexity (ECCC), 23:100, 2016. URL: http://eccc.hpi-web.de/report/2016/100.
  45. Roei Tell. Proving that prBPP=prP is as hard as "almost" proving that P ̸ = NP. Electronic Colloquium on Computational Complexity (ECCC), 25:3, 2018. URL: https://eccc.weizmann.ac.il/report/2018/003.
  46. Roei Tell. Quantified derandomization of linear threshold circuits. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 855-865, 2018. URL: https://doi.org/10.1145/3188745.3188822.
  47. R. Ryan Williams. Natural Proofs versus Derandomization. SIAM J. Comput., 45(2):497-529, 2016. URL: https://doi.org/10.1137/130938219.
  48. Richard Ryan Williams. Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds, ReLUs, and Low-Degree Polynomials. In 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, pages 6:1-6:24, 2018. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.6.
  49. Ryan Williams. Improving Exhaustive Search Implies Superpolynomial Lower Bounds. SIAM J. Comput., 42(3):1218-1244, 2013. URL: https://doi.org/10.1137/10080703X.
  50. Ryan Williams. Towards NEXP versus BPP? In Computer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013. Proceedings, pages 174-182, 2013. URL: https://doi.org/10.1007/978-3-642-38536-0_15.
  51. Ryan Williams. New algorithms and lower bounds for circuits with linear threshold gates. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 194-202, 2014. URL: https://doi.org/10.1145/2591796.2591858.
  52. Ryan Williams. Nonuniform ACC circuit lower bounds. Journal of the ACM (JACM), 61(1):2, 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact