Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity Lijie Chen Ryan Williams Context: The Algorithmic Method for Proving Circuit Lower Bounds Proving limitations on non-uniform circuits is extremely hard. Prior approaches (restrictions, polynomial approximations, etc.) face barriers (Relativization, Algebrization, Natural Proofs). Algorithmic Method Non-trivial circuit-analysis algorithm Circuit Lower Bounds. Breakthroughs where previous approaches failed (NEXP ACC0). Believed to be possible for strong circuits (even ).

Context: A Frontier of Circuit Complexity, Depth-2 Threshold Circuits THR gates : , . MAJ gates : when s and are bounded by poly(n). THRTHR We can also define THR THR THR THR Context: A Frontier of Circuit Complexity, Depth-2 Threshold Circuits

Exponential Lower Bounds are known for [Hajnal-Maass-Pudlk-Szegedy-Turn93] [Nisan94] [Forster-Krause-Lokam-Mubarakzjanov-Schmitt-Simon01] NEXP Non-deterministic Exponential Time. Frontier Open Question: Is NEXP ? Potential Approaches in this talk. Motivation: Apply the Algorithmic Method to THR of THR? What Circuit-Analysis Tasks? -SAT

Derandomization!! x s.t. time? ? -CAPP Non-trivial CircuitAnalysis Algorithms Circuit Lower Bounds Estimate quantity ,

with additive error : constant or inverse polynomial Motivation: Apply the Algorithmic Method to THR of THR? Most previous work on the algorithmic method exploits SAT algorithms. THRTHR Problem SAT of THR of THR is probably very hard. A special case is MAX--SAT, for which no nontrivial ( time) algorithm is known for and clauses. Considered to be a barrier for the Algorithmic Approach. THR

THR THR THR MAX--SAT MAJ Motivation: Apply the Algorithmic Method to THR of THR? SAT of THR of THR

From Derandomization (CAPP) : probably very hardCircuit Lower Bounds For a circuit class , But derandomization is widely believed to be possible. NQP Non-deterministic Quasi-Polynomial Time. -time CAPP for () [Williams13/14, Santhanam Williams14, Ben-Sasson Viola14]

-time CAPP for () cant be -approximated by [R. Chen Oliveira Santhanam18] -time CAPP for () [Murray Williams18] -time CAPP for () cant be -approximated by [L. Chen19]

Back to THR of THR SAT of THR of THR : probably very hard To show , we need to derandomize , which could be harder. Our result 1 It suffices to derandomize . Our result 2 Surprisingly, it indeed only suffices to derandomize or ! General Result: A Stronger Connection Between CircuitAnalysis Algorithms and Circuit Lower Bounds For a circuit class : -time CAPP for , , or . -time CAPP for , , or

. Why the constant 2? Short answer: A PCP system needs to make at least queries. Long answer: See the paper Tighter Connections for Algorithms/Lower Bounds for THR of THR Luckily, the 2 doesnt matter for -time CAPP algorithm for . -time CAPP algorithm for .

: depth-d, poly-size, linear threshold circuits Let Us Make Our Life Even Easier Poly-size and are equivalent for Non-Trivial ( time) CAPP Algorithms when THR THR THR MAJ THR MAJ

Proved by new structure lemmas for MAJ MAJ Let Us Make Our Life Even Easier Poly-size and are equivalent for Non-Trivial ( time) CAPP Algorithms for any constant ! THR THR THR THR

THR MAJ Proved by new structure lemmas for MAJ MAJ Corollary If there are -time CAPP for with , or a -time CAPP for with constant , then .

Another Application: Inapproximability by Depth-2 Neural Networks Depth-2 Neural Network ( ) ( ) 1 THR 2

THR ( ) ( ) 1 ReLU 3 2 ReLU Thm For every and constant ,

there is a function such that cannot be approximated by Depth-2 Neural Networks of size THR 3 ReLU Improved [Wil18], which proved that there is such an which cannot be exactly computed by Depth-2 Neural Networks of size . Philosophy Using PCP Algorithmically to Prove Circuit Lower Bounds (Remember: PCPs are algorithms!) If you want to prove , then PCPs should make your life much

easier (now you only need an algorithm for -approximation to 3SAT!) [Hstad97] (Well, I dont really believe in .) We only want to derandomize circuits. But PCPs still make our life easier (though in a more indirect way) Starting Point: Non-deterministic Derandomization Suffices for Circuit Lower Bounds -GAP-TAUT (tautology) [Wil13] time nondeterministic algorithm Distinguish between for GAP-TAUT on poly-size 1. Non-deterministic Algorithmgeneral for GAP-TAUT circuits with (Yes Case)

Given a general circuit , we want a time . 2. . non-deterministic algo , such that: (No Case) 1. If is a tautology, then accepts on some guesses. 2.If, rejects on all guesses. Proof Overview: Outline Starting Point [Wil13] Key point: make use of for GAP-TAUT on poly-size time non-deterministic algorithm

this assumption as general circuits with much as possible! . Assume Think of as Non-trivial CAPP on with constant non-deterministic GAP-TAUT for Contradiction! Goal: Designing the Algorithm under Assumption Assume

non-deterministic GAP-TAUT on Think of as Non-trivial CAPP on with constant It is universal Goal Given an circuit , under the two assumptions, design a time non-deterministic algo , such that: 1. If is a tautology, then accepts on some guesses. 2. If , rejects on all guesses. Review: Approach of [Wil14] Guess-and-Verify-Equivalence implies collapses to . That is, under assumption, the given general circuit has

an equivalent circuit . If we can find , then we can derandomize instead, where we have algorithms! Problem: How to find ? Allowed to use non-determinism so one can guess . But still have to verify is equivalent to , which seems HARD. Solution Well, just guess more circuits! Review: Approach of [Wil14] Guess-and-Verify-Equivalence Suppose has gates, let be the corresponding subcircuits. 1. is the output gate.

2. are inputs. implies collapses to . We guess circuits , hoping that . We wish to check . To do this, for each , suppose gate- has inputs from gate- and gate-. We verify . Then run CAPP on . Problem Checking for all requires solving SAT for . A Local-checkable Proof System View Problem: the previous approach requires solving SAT for . Let What is so good about this proof ? This is a Claimed Proof for by giving

values at all gates. Intuitively, it is supposed to be the computation history of on input . Local checks on For each , . A Local-checkable Proof System View Let A Claimed Proof for by giving values at all gates. One can get functions on , such that Each is an of 3 bits (or their negations) from . If on the correct guesses , all s are satisfied by . (Completeness) If , for all possible at least one is not satisfied by . (Soundness)

An Attempt Guess circuits , let Estimate . (.) (:number of s) If is a tautology. Then on the correct guess, If then on all guesses, . To distinguish the above two cases, we need a CAPP algo with error . But we only assume a CAPP algo with constant error! What Went Wrong? Proof System View One can get functions on , such that Each is an of 3 bits (or their negations) from . If on the correct guess , all s are satisfied: by . (Completeness a claimed

proofis 1) of If , for all possible at least one is not: satisfied local check of the verifier by . (Soundness is ) If there is a verifier who picks a random and checks whether . She detects an error only with probability when . This is an extremely ``bad PCP! Why not just use the PCP theorem? Issues When Applying PCPs Directly Recall that in the end we want to estimate Use PCPs of Proximity!

Like PCPs but both input and Key properties being used in previous attempt: proof are given as oracles. These local checks (verifiers queries positions) do not depend on the input ! PCPs V (input) PCPs of Proximity (input) Unlimited access 3 queries (proof)

Now, can depend on many bits of . V 3 queries in total (proof) ( ( ) ) 3 Issues When Applying PCP Directly Therefore, we want a proof system for verifying , such that given the random bits, verifier queries both input and proof . 1. If , , such that always accept. 2. If , , rejects w.h.p. Counter-example?

Suppose computes the parity. Parity changes if we flip a random bit of . The verifier cant distinguish unless she queried that bit. Solution Give access to an error correcting code of ! Combing PCP of Proximity and ECCs PCP of Proximity How it avoids the parity Verifier is given both the input () and the proof as oracles and counter example? makes queries.

accepts w.p. 1, when ; No inputs can make parity accepts w.p. , when makes robustly output ( is zero in a !small robustly output hamming ball around ). (like property testing) (input) V 3 queries in total (proof) PCP of Proximity with ECCs

Verifier is given both the encoded input () and the proof as oracles and makes queries. accepts w.p. 1, when ; accepts w.p. , when . Use of Proximity for verifying , makes robustly output when ! DEC(corrupted ) is still Final Algorithm Guess circuits , let constant Fix to be -linear. That is, is a parity on a subsetNow of bits in . error CAPP algo for suffices!

Suppose there is uniform parity circuit in for now (this assumption can be avoided) Estimate . (.). If is a tautology. Then on the correct guesses, If then on all guesses, . Future Work NEW Building on the PCPP based approach, [Alman Chen19] give a construction of Razborovrigid matrices in . Can we find non-trivial CAPP algorithms for or to prove circuit lower bounds for ? Recall: we know exponential lower bounds for these two models! Can we ``mine some algorithms from these proofs? Thank You