Circuit Lower Bounds and Algorithm Techniques

Algorithms vs. Circuit Lower Bounds Igor Carboni Oliveira Columbia University CCI Meeting Princeton, February 2014

What this talk is about Explicit function f(P, EXP, NP, ) not in nonuniform circuit class (ACC, TC0, NC1, ). Algorithm for hard computational problem Sketch some proof techniques used in different contexts + point out some observations from [O 13] + mention some directions.

This talk: Compression Important: No assumptions on algorithm. Learning Satisfiability Non-uniform Circuit Lower Bounds Discuss techniques for deterministic, nondeterministic, randomized algorithms. Why should you care? Nontrivial proofs for tautologies Derandomization only known approach to some CLBs. Useful Properties (CLBs around NEXP)

Recall that: MAEXP not here! [BFT 98] NEXP not here! [Williams 11] Contains NEXP? AC0 ACC TC0 NC1 AC1 NC2 P/poly a few nontrivial (restricted) SAT algorithms [IPS13], [Williams 14], Learning algorithm [LMN 89] SAT algorithm [Williams 11] P NP PH PSPACE EXP NEXP, BPEXP MAEXP NEXP, BPEXP TC0 (depth two)? TC0 (depth two)? Open.

A warm-up example

80s: super fast SAT implies strong CLBs [Karp-Lipton-Meyer 80] + [Kannan 82] If P = NP then EXP requires circuits of exponential size. Proof sketch. 1) P = NP implies P = PH (easy). 2) P = PH implies EXP = EXPH (padding). 3) EXPHcontains problems of exponential circuit complexity [Kannan 82]. Strong lower bound from a very strong assumption.

Three decades later

Nontrivial proofs for C-tautologies implies CLBs Roadmap (*approximate*) BFNW 93, NW 94, IW 97, Hardness vs. Randomness Circuit lower bound obtained from new algorithm. Kabanets 01: Easy witness method Know even more about ACC! EXP ACC or NTIME[nlogc n] ACC. Williams 11: C-SAT Algorithms, NEXP ACC. IKW 02: NEXP vs. P/poly Williams 10: nontrivial P/poly- SAT algorithms and lower bounds Tourlakis 01, FLvMV 05: Tight Cook-Levin reduction Yao 90, BT 94, AG 94: Structural results for ACC.

A closer look: Nontrivial proofs imply CLBs Proposition ([Williams 11], Informal). Let C be a circuit class. If there exists a proof system P such that every polynomial size tautology over n variables from C admits a proof that can be checked in time 2n/s(n), then NEXP C. Deterministic SAT algorithms: particular case. *Find* proofs in time 2n/s(n). Formally: What is a circuit class? C = TC0 depth two? C C (loss in the reduction).

Nontrivial proofs imply CLBs [Williams 10] C = C = P/poly. [Williams 11] C contains AC0, closed under composition. Proofs for tautologies in depth 2d + O(1) imply CLBs for depth d. ACC lower bound. Next step: lower bounds against classes such as depth-two TC0? [O 13] Relax assumptions on C + tighter connection + simpler proof: Proofs for depth d + 2 yield circuit lower bounds against depth d . NEXP ACC o TH [Willliams 14]. Proof explores trick introduced in [O 13].

Def. A circuit class C is reasonable if: Examples: depth-d TC0, AC0, NC1, P/poly. 1. The constant function 0 is in C; 2. C is (effectively) closed under complementation; 3. Gates may have direct access to constant inputs 0/1; 4. C P/poly. = Computational Problem: Equiv-AND-C Def. Given circuits f, g, h from C, check if: AND f (x) AND g(x) = h(x), for every x in {0,1}n. h f g Def. Nontrivial proofs: can be checked by a uniform algorithm in time 2n/s(n). Tautology? Proposition [O 13]. If C is reasonable and polynomial size EQUIV-AND-Ctautologies admit nontrivial proofs, then NEXP C.

Proposition [O13]. If C is reasonable and polynomial size EQUIV-AND-C tautologies admit nontrivial proofs, then NEXP C. Proof sketch (following [Williams 10]). NTIME[2n] NTIME[2n/n100] (1)NEXP C (2) nontrivial proofs. Assume: We contradict the Nondeterministic Time Hierarchy Theorem. Lemma 1 (Tourlakis 01, FLvMV 05: tight Cook-Levin reduction ). Every language L NTIME[2n] can be reduced to (succinct)3SAT instances of size poly(n)2n. There is a polynomial time algorithm that, given x (instance of L), outputs a circuit CX from P/poly over n + O(log n) inputs that: 1) Given an index i {0,1}n + O(log n), CX prints the i-th clause of formula FX. x L. 2)FX is satisfiable FX : exponentially many clauses and variables. Succinct representation given by circuit CX.

Proposition [O13]. If C is reasonable and polynomial size EQUIV-AND-C tautologies admit nontrivial proofs, then NEXP C. (C is reasonable ) Recall: NEXP C P/poly Proof sketch. Lemma 2 (IKW 02, hardness vs. randomness, easy witness, diagonalization ). If NEXP P/poly then every NEXP-verifier V admits succinct witnesses: If V(x,w) = 1 for some w (of exponential length), then there is some w* such that: 1) V(x,w*) = 1; 2) w* is the truth table of some polynomial size circuit D. Lemma 2 implies that: FX is satisfiable FX(tt(D)) = 1, for some circuit D from P/poly over n + O(log n) variables.

How to check whether FX is satisfiable? Proposition [O 13]. If C is reasonable and polynomial size EQUIV-AND-C tautologies admit nontrivial proofs, then NEXP C. Build a new circuit. Recall: Trying to decide L NTIME[2^n] in less (nondeterministic) time. Given instance x, poly size circuit CX prints i-th clause of 3-CNF FX. (Nondeterministic) Algorithm for L: Guess circuit D that outputs assignment for FX. Combines circuits CX and D into a new circuit EX over n + O(log n) variables such that: EX : Given input i (index of a clause), use CX to print this clause, and three copies of D to obtain values for variables in this clause. EX outputs 1on input i {0,1}n + O(log n) i-th clause is satisfied by D Therefore: x in Liff FX satisfiableiff P/poly circuit D with FX(tt(D)) = 1iff EX is a tautology

Proposition [O13]. If C is reasonable and polynomial size EQUIV-AND-C tautologies admit nontrivial proofs, then NEXP C. Proof sketch. x in L EX is a tautology So far: poly time computation + guessing D (poly size string) = NP computation. Problem: How to prove that EX is a tautology and put L in NTIME[<<2n]? EXis a P/poly-circuit . [Williams 10] [Williams 11] [SW 12] [JMV 13] [SV 14] How to obtain an equivalent circuit from circuit class C? We describe next the method from [O 13].

Proposition [O13]. If C is reasonable and polynomial size EQUIV-AND-C tautologies admit nontrivial proofs, then NEXP C. Proof sketch. Fact. By assumption P NEXP C. Therefore any function f: {0,1}n to {0,1} computed by a P/poly circuit A of size na admits a circuit from C of size nb. Why? Circuit evaluation problem is in P (instances: <circuit, input>), and P C. Equiv-AND-C IMPORTANT: function computed at this AND gate admits C-circuits of size nb. HardwireA s description in new circuit from C computing Circuit evaluation . AND NOT Circuit EX: We can assume EX uses AND (fan-in two), NOT gates only. Every subcircuit of EX has size na. Guess equivalent C- circuits of size nb. =? AND Use nontrivial EQUIV-AND_C proofs to check that these circuits are equivalent. f in C g in C NOT AND h in C Obtain final C-circuit H equivalent to EX. Finally, guess a proof that H is a tautology. AND NOT

An example from derandomization: PIT

Derandomization implies CLBs [KI 04] PIT = language of all arithmetic circuits computing zero polynomial over Z. PERM = problem of computing the permanent over integer matrices. Proposition. If PIT NSUBEXP, then at least one of the following results hold: (1) NEXP P/poly; or (2) PERM AlgP/poly. Follows from downward reducibility of Permanent! Let s derive it from William s theorem. Lemma [KI 04], [AvM 11]. There exists an efficient algorithm such that: Input: Arithmetic Circuit An. Output: Arithmetic Circuit Cm. Guarantee:An computes PERM of n x n matrices iffCm PIT.

Proposition [KI04] . If PIT NSUBEXP, then at least one of the following results hold: (1) NEXP P/poly; or (2) PERM AlgP/poly. EXP P/poly Proof by contradiction. Assume PIT NSUBEXP, NEXP P/poly, PERM AlgP/poly. [Williams 10] (contrapositive): If NEXP P/poly then P/poly tautologies admit only trivial proofs. Subexponential size proofs for P/poly tautologies: EXP P/poly MetaMetaTheorem [O 13]: Proof shows that these meta results are in fact connected: Given poly size circuit C, is C a tautology? Problem in PH. By Toda s Thm, reduces to P#P. By Valiant s Thm, reduces to PERM. Since PERM AlgP/poly, can guess a small arithmetic circuit A for PERM. Using previous Lemma, can check if A is correct by solving PIT (in NSUBEXP). Answer initial query (correctly!). Improvements in Williams framework propagate to [KI 04]. Connection may even improve [KI 04] (work in progress)

Easier way to prove meta theorems of the form algorithm implies circuit lower bounds ? Useful Properties [Williams 13]: Characterizing CLBs around NEXP . Def.Property of Boolean functions = subset of all Boolean functions. A property is useful against circuit class C[poly] if: k infinitely many n s such that: 1) (fn) = 1 for at least one function fn: {0,1}n to {0,1} 2) (gn) = 0 for all gn : {0,1}n to {0,1} computed by circuits from C of size nk. We say that is a -Property if it can be decided in complexity class (on inputs of size N = 2n). f C distinguishes a hard function f from all functions in C.

Useful Properties versus Circuit Lower Bounds A P-property is an algorithm! [Williams 13] There exists a P-property useful against C iff NEXP C . If we insist that useful properties are defined only over truth tables, i.e., inputs of size N = 2n (following previous definition), then: What matters for this talk: Proposition 1. There exists a P/log N-property useful against C[poly]iffNEXP C[poly]. Algorithm running in time polynomial in N (truth table size) that distinguishes hard function from functions in C[poly]: What if we insist on properties computed without advice? [O 13] Proposition 2. a) If for every constant d there exists a P-property useful against C[nlogd n], then NE i.o.coNE C[nlog n]. b) If NE coNE C[poly] then there is a P-property useful against C[poly]. NEXP C[poly]. Check [O 13] for more details.

Some direct consequences (I) Deterministic! [FK 06] Learning yields circuit lower bounds Proposition. Let C be any circuit class. If there exists a subexponential time algorithm that exact learns any concept from C using MQ and EQ queries, then EXPNP C. Equivalence Query oracle EQf: Given (the representation) of a function g:{0,1}n -> {0,1}, outputs yes if g f, or an input w such that g(w) f(w) otherwise. Membership Query oracle MQf: Given any x {0,1}n, returns f(x). Original Proof: Karp-Lipton Collapse, Properties of PERM, Relativized Time Hierarchy, + other ideas All functions in C: learned in time << 2n. Random function:cannot be learned in time << 2n. Given truth table of size N = 2n, try to learn it. Efficient algorithm in N (can answer MQ and EQ). P-property useful against C. NEXP C.

Some direct consequences (II) [KK 13, CKKSZ 13] Approximate Compression yields circuit lower bounds Problem: C[poly] circuit class. Given the truth-table of a function f in C (of size N= 2n), output in time poly(N) a circuit of size <<2n/n that 0.51-approximates f. Proposition. If C admits efficient compression algorithms, then NEXP C[poly]. Using the same argument, follows immediately from Useful Properties : random functions cannot be compressed (not even approximately). This approach is not always optimal! Exact learning leads to stronger lower bounds: elementary proof in [KKO 13]. Using [O 13], compression of quasi-poly size circuits from C yields even stronger CLBs!

CLBs from randomized algorithms

CLBs from randomized (learning) algorithms Proposition [FK 06]. Let C P/poly be any circuit class. If C is PAC-learnable with membership queries under the uniform distribution in polynomial time, then BPEXP C[poly]. Proposition [KKO 13]. If C is PAC learnable with membership queries under the uniform distribution in polynomial time, then either: (1) PSPACE C[poly]; or (2) PSPACE BPP. Can be combined with [Santhanam 07] to get lower bounds for BPP/1[Volkovich 14] Removing (2) from statement implies PSPACE BPP (unconditionally)

Proposition [KKO13]. If C is PAC learnable with membership queries under the uniform distribution in polynomial time, then either: (1) PSPACE C[poly]; or (2) PSPACE BPP. Assume: C is learnable + PSPACE C[poly]. Need to prove that PSPACE BPP. Plan: Let f be a PSPACE-complete function in C[poly]. Use efficient (randomized) learning algorithm to compute f in BPP .

Problem 1: (PAC) Learner provides hypothesis that is correct on 99% of the inputs. Can correct hypothesis from learner! BPP Algorithm: must be correct on every input (with high probability). Idea: There is a PSPACE-complete problem f that is self-correctible [BF 90]: if hypothesis for f is correct on most inputs, then can compute f correctly on every input x with high probability. Problem 2: Learning algorithm asks MQs: given x, what is f(x)? Exactly what we are trying to compute! g = TQBF! Idea: There is a PSPACE-complete problemg that is downward self-reducible: Can compute g(x) in polynomial-time if can compute g on smaller instances. Theorem [TV 07]. There exists a language L* such that: 1) L* is PSPACE-complete. 2) L* is self-correctible. 3) L* is downward self-reducible. Can answer MQs if can compute g on smaller instances!

Limitations of these approaches Which algorithms can lead to newCLBs? Narrow view combine different techniques! Learning. black-box. No PRFs in circuit class C. Compression. Natural proofs barrier as well... Derandomization of PIT. Extensions.Strong algorithmic assumption? Satisfiability. Non black-box. Weak assumption. Partial progress on TC0. What about NC1? P/poly? Stronger CLBs? Hard to design algorithms

Designing nontrivial algorithms in the CLB World ? Algorithms used in previous CLB proofs can be implemented! CLB connection Complexity Theory Framework Design of Algorithm A very simple example from learning theory. Membership Queries versus Random Examples. DNFs learnable in poly time under the uniform distribution with MQs [Jackson 94]. Can we learn DNFs efficiently using random examples? Open.

Designing nontrivial algorithms in the CLB World? In a circuit lower bound proof, everything that can be learned with MQs in poly time can be learned with random examples only. Proof sketch. CLB proof against C: can assume from the very beginning that PSPACE C. [KKO 13] CPAC-learnable with MQs in poly time then either: PSPACE C[poly] or PSPACE BPP. Therefore learning C with MQs implies PSPACE BPP. But then C can be learned with random examples only by finding a consistent hypothesis ( Occam s Razor ).

Final Remarks Use assumption? Can we design nontrivial algorithms using the extra power provided by our assumption ( no CLB )? Help from proof complexity? Easier than obtaining deterministic SAT algorithms? Partial converse to Williams program? Is the existence of nontrivial proofs *necessary* for CLBs against C? Suppose NP C, and that this proof can be formalized in some bounded arithmetic theory. Q. Is it the case that every C-tautology admits a nontrivial proof?

Thank you! Thank you!