Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
© Lijie Chen and R. Ryan Williams; licensed under Creative Commons License CC-BY 34th Computational Complexity Conference (CCC 2019). We considerably sharpen the known connections between circuit-analysis algorithms and circuit lower bounds, show intriguing equivalences between the analysis of weak...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137603 |
| _version_ | 1826201224331919360 |
|---|---|
| author | Williams, Richard Ryan Chen, Lijie |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Williams, Richard Ryan Chen, Lijie |
| author_sort | Williams, Richard Ryan |
| collection | MIT |
| description | © Lijie Chen and R. Ryan Williams; licensed under Creative Commons License CC-BY 34th Computational Complexity Conference (CCC 2019). 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 ◦ THR lower bounds (a notorious open problem), by connecting algorithmic analysis of THR ◦ THR to the provably weaker circuit classes THR ◦ MAJ and MAJ ◦ MAJ, where exponential lower bounds have long been known. More precisely, we show equivalences between algorithmic analysis of THR ◦ THR and these weaker classes. The ε-error CAPP problem asks to approximate the acceptance probability of a given circuit to within additive error ε; it is the “canonical” derandomization problem. We show: There is a non-trivial (2n/nω(1) time) 1/poly(n)-error CAPP algorithm for poly(n)-size THR ◦ THR circuits if and only if there is such an algorithm for poly(n)-size MAJ ◦ MAJ. There is a δ > 0 and a non-trivial SAT (δ-error CAPP) algorithm for poly(n)-size THR ◦ THR circuits if and only if there is such an algorithm for poly(n)-size THR ◦ 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 (2n/nω(1) time) CAPP for ORpoly(n) ◦ AND3 ◦ C yields NEXP 6⊂ C. 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 2 ◦ C, AND2 ◦ C or OR2 ◦ C. A direct corollary of the first two bullets is that NEXP 6⊂ THR ◦ THR would follow from either: a non-trivial δ-error CAPP (or SAT) algorithm for poly(n)-size THR ◦ MAJ circuits, or a non-trivial 1/poly(n)-error CAPP algorithm for poly(n)-size MAJ ◦ 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 ε > 0, we prove there are Boolean functions f computable in nondeterministic nlog 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 maxx∈{0,1}n |N(x) − f(x)| > 1/2 − ε. 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 ◦ THR circuits, and linear combinations of low-degree Fp polynomials. These results constitute further progress towards THR ◦ THR lower bounds. |
| first_indexed | 2024-09-23T11:48:31Z |
| format | Article |
| id | mit-1721.1/137603 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:48:31Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1376032023-12-07T18:13:40Z Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity Williams, Richard Ryan Chen, Lijie Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © Lijie Chen and R. Ryan Williams; licensed under Creative Commons License CC-BY 34th Computational Complexity Conference (CCC 2019). 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 ◦ THR lower bounds (a notorious open problem), by connecting algorithmic analysis of THR ◦ THR to the provably weaker circuit classes THR ◦ MAJ and MAJ ◦ MAJ, where exponential lower bounds have long been known. More precisely, we show equivalences between algorithmic analysis of THR ◦ THR and these weaker classes. The ε-error CAPP problem asks to approximate the acceptance probability of a given circuit to within additive error ε; it is the “canonical” derandomization problem. We show: There is a non-trivial (2n/nω(1) time) 1/poly(n)-error CAPP algorithm for poly(n)-size THR ◦ THR circuits if and only if there is such an algorithm for poly(n)-size MAJ ◦ MAJ. There is a δ > 0 and a non-trivial SAT (δ-error CAPP) algorithm for poly(n)-size THR ◦ THR circuits if and only if there is such an algorithm for poly(n)-size THR ◦ 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 (2n/nω(1) time) CAPP for ORpoly(n) ◦ AND3 ◦ C yields NEXP 6⊂ C. 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 2 ◦ C, AND2 ◦ C or OR2 ◦ C. A direct corollary of the first two bullets is that NEXP 6⊂ THR ◦ THR would follow from either: a non-trivial δ-error CAPP (or SAT) algorithm for poly(n)-size THR ◦ MAJ circuits, or a non-trivial 1/poly(n)-error CAPP algorithm for poly(n)-size MAJ ◦ 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 ε > 0, we prove there are Boolean functions f computable in nondeterministic nlog 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 maxx∈{0,1}n |N(x) − f(x)| > 1/2 − ε. 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 ◦ THR circuits, and linear combinations of low-degree Fp polynomials. These results constitute further progress towards THR ◦ THR lower bounds. 2021-11-05T19:44:01Z 2021-11-05T19:44:01Z 2019 2021-03-24T17:44:38Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137603 Williams, Richard Ryan and Chen, Lijie. 2019. "Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity." Leibniz International Proceedings in Informatics, LIPIcs, 137. en 10.4230/LIPIcs.CCC.2019.19 Leibniz International Proceedings in Informatics, LIPIcs Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf DROPS |
| spellingShingle | Williams, Richard Ryan Chen, Lijie Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity |
| title | Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity |
| title_full | Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity |
| title_fullStr | Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity |
| title_full_unstemmed | Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity |
| title_short | Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity |
| title_sort | stronger connections between circuit analysis and circuit lower bounds via pcps of proximity |
| url | https://hdl.handle.net/1721.1/137603 |
| work_keys_str_mv | AT williamsrichardryan strongerconnectionsbetweencircuitanalysisandcircuitlowerboundsviapcpsofproximity AT chenlijie strongerconnectionsbetweencircuitanalysisandcircuitlowerboundsviapcpsofproximity |