Chen, Lijie ;
Williams, R. Ryan
Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity
Abstract
We considerably sharpen the known connections between circuitanalysis 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 depthtwo 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 epsilonerror 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 nontrivial (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 nontrivial SAT (deltaerror 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 depthd linear threshold circuits and depthd MAJORITY circuits. These equivalences are proved via new simulations of THR circuits by circuits with MAJ gates.
 We strengthen the connection between nontrivial derandomization (nontrivial CAPP algorithms) for a circuit class C, and circuit lower bounds against C. Previously, [BenSasson and Viola, ICALP 2014] (following [Williams, STOC 2010]) showed that for any polynomialsize class C closed under projections, nontrivial (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 nontrivial 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 nontrivial deltaerror CAPP (or SAT) algorithm for poly(n)size THR o MAJ circuits, or
 a nontrivial 1/poly(n)error CAPP algorithm for poly(n)size MAJ o MAJ circuits.
 Applying the above machinery, we extend lower bounds for depthtwo 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 polynomialsize depthtwo neural network N on n inputs (with sign or ReLU activation) must satisfy max_{x in {0,1}^n}N(x)f(x)>1/2epsilon. 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 lowdegree F_p polynomials. These results constitute further progress towards THR o THR lower bounds.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2019:10841,
author = {Lijie Chen and R. Ryan Williams},
title = {{Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {19:119:43},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771160},
ISSN = {18688969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10841},
URN = {urn:nbn:de:0030drops108419},
doi = {10.4230/LIPIcs.CCC.2019.19},
annote = {Keywords: PCP of Proximity, Circuit Lower Bounds, Derandomization, Threshold Circuits, ReLU}
}
2019
Keywords: 

PCP of Proximity, Circuit Lower Bounds, Derandomization, Threshold Circuits, ReLU 
Seminar: 

34th Computational Complexity Conference (CCC 2019)

Issue date: 

2019 
Date of publication: 

2019 