CS294-152 Lower Bounds
11/5/18
===
How Circuit Analysis Implies Circuit Lower Bounds

Announcements:

*** Confirmed a few hours ago:
Extra lecture on Friday @ Simons Institute, room 116, 5pm - 6:30 ish 
i.e. 4:50 Berkeley time - 6:30 ish
Please come a little early if possible before the doors lock at 5... if they do, just email me or contact me on hangouts (I’m rrwilliams found at gmail.com)

*** Scribes: Don't forget to send your notes to me! :)

*** Who scribes today? Friday? November 19th? (No class next week)
 Anyone left? :) 

===

Last time:

— Thm [Beigel-Tarui 91 (building on Yao)]
For every symmetric function f, there is a symmetric function f'
s.t. f of s AC0[m] circuits of size s and depth d can be represented as a f' of s^{polylog(s)} ANDs, where the polylog factor depends on d and m.

“ACC^0 is in quasi-poly SYM of ANDs”

Let AC^0_d[m] = AC circuits of depth d with AND/OR/NOT/MODm gates.

— Thm [W'11] For all d and m, there is a delta > 0 such that:
the SAT problem for AC^0[d] circuits of size 2^{n^{delta}} can be solved in 2^{n-n^{delta}} time.

“ACC^0 SAT is in 2^{n-n^{delta}} time”

We also briefly discussed generic “circuit-analysis problems”:
— C-SAT: Given a circuit D from class C, is D satisfiable?
It’s NP-complete for almost all interesting C.

— Gap-C-SAT: Given a circuit D from class C, 
promised D is UNSAT or has >= 1/2 of its assignments satisfying, determine which. 
This is the canonical “RP” problem: random samples distinguish the cases whp.
(Technically the corresponding class is called "Promise-RP".)
Gap-C-SAT is widely believed to be in P, even for C = generic circuits!

We talked informally about how these might be used to prove lower bounds.
Today we’ll look at that more concretely.

===

How could we use faster circuit-analysis algorithms to prove circuit lower bounds?

Here's a starting thm, which will play a significant role in further discussions.

Thm [KL'80, attributed to Meyer] If P = NP then TIME[n^{log n}] is not in P/poly.

This theorem can be viewed as saying:
--- Suppose Circuit SAT is in polynomial time. Then there is a super-efficient algorithm to tell if a given circuit implements a trivial function or not.
--- With this algorithmic ability, quick algorithms are very powerful. We can use quick algorithms to find a function computable in n^{log n} time that does not have a poly-size circuit family.

***
Note: Way back in lecture 2, we proved a stronger-looking theorem:
Thm [Folklore] If P = NP then TIME[2^{O(n)}] is not in SIZE(Omega(2^n/n)). 
This argument also yields: 
Thm If P = NP then TIME[n^{O(log n)}] is not in SIZE(Omega(n^{log n})).

That proof worked by using the facts: 
- E^{Sigma_2 P} not in SIZE(Omega(2^n/n))
and 
- P = NP ==> Sigma_2 P = P
The following proof, which is quite different, 
seems much more *adaptable* to faster SAT algorithms than the one we saw.
Although I would not be surprised if we could somehow adapt the old proof!
Nice open problem...
***

These theorems have an interesting connection between algorithms and lower bounds, 
but they seem to have limited utility for *actually proving* lower bounds! 
The theorem has the form

"If pigs can fly (P = NP) then pigs can oink (TIME[n^{log n}] is not in P/poly)"

If an unexpected breakthrough happens, then a completely expected result happens.

Nevertheless, the alternative proof we give is a stepping stone to something much more interesting.
Our alternative proof starts with the following very simple observations:

Easy Witness Lemma for n^{log n} time:
TIME[n^{log n}] is in P/poly => 
"For every n^{log n}-time TM M and every input x, 
there are small circuits encoding the computation history of M running on x"

Formally: For every one-tape TM M using O(n^{log n}) time,
there is a poly-size circuit family {C_n} such that
for all x in {0,1}*, i,j, C_{|x|}(x,i,j) outputs the content of the j-th cell during the i-th step of M(x).
In other words, C_{|x|}(x,i,j) outputs the (i,j) cell of the *tableau* of M(x).

Pf of EWL:
Define f_M(x,i,j) := "Simulate M(x) for i steps. Output content of the jth cell."
f_M is in n^{O(log n)} time. By assumption, f_M has a poly-size circuit family. QED

We call the above an "easy witness lemma" because a computation history of M on x is a "witness/proof" that M halts and gives a particular answer. So the lemma says:
 "Small circuits for n^{log n} time imply succinct *witnesses/proofs* of n^{log n} computations"

Pf of Thm: 
(BTW I do not think this is not the original proof... I am not sure who it is due to, but I know I observed it...)
Assume (A) P = NP
and (B) TIME[n^{log n}] is in P/poly. We want to get a contradiction.

At a very high level, our strategy will be similar to the SAT time-space tradeoffs.
We will show (A) and (B) imply
TIME[n^{(log n)/2}] is in P, contradicting the time hierarchy theorem.

Let M be a TM running in n^{(log n)/2} time.
First, convert M into a one-tape TM running in n^{log n} time. WLOG this TM ends in the leftmost tape cell when it halts.

Next, note that (B) and EWL for M => small circuits encoding the history of M
We can use EWL to get a Sigma_2 P simulation of M. 
In particular, we can guess circuits encoding the computation history, and verify them in coNP:

M(x) accepts <=>
(There is a circuit C of poly(|x|) size)
[C(x,n^{log n},1) is in an accept state] & (Forall j)[C(x,0,j) is consistent with initial config of M(x)]
& (Forall i != 0,j)[C(x,i,j) is consistent with C(x,i-1,j-1),C(x,i-1,j),C(x,i-1,j+1)]

Key point: Since M is a one-tape TM, all computation is local, i.e., we only need to look at the cells (i-1,j-1),(i-1,j),(i-1,j+1) to determine what the content of cell (i,j) should be.

Note: so far, we have proved TIME[n^{log n}] is in P/poly => TIME[n^{log n}] is in Sigma_2 P.
Similar to the Karp-Lipton Theorem, which showed NP is in P/poly implies PH = Sigma_2 P.

Now, the RHS of the above condition on M(x) is a Sigma_2 P computation: 
We are guessing a circuit C, then universally trying a bunch of conditions on C, where each condition is checked in polynomial time.
Now, (A) => Sigma_2 P = P. So M can be simulated in P.
This is a contradiction, as M was chosen to be an arbitrary n^{(log n)/2}-time TM!
QED

Goal: relax the P=NP hypothesis, and replace it with a hypothesis that's possibly true!

— Suppose we only assume NP is in 2^{o(n)} time. 
The proof above would break, because we had to apply the assumption P=NP twice, to get Sigma_2 P = P.

If NP is in 2^{o(n)} time, then we *don’t* necessarily have Sigma_2 P in 2^{o(n)} time!

Well, we do achieve a strong conclusion (n^{log n} time not in P/poly) in the above, 
when we don’t even know if NEXP is in P/poly or not.
So let’s try to see what algorithmic hypotheses would imply lower bounds on NEXP instead.

What might that look like?
Here is one approach, trying to mimic the above proof:
(A) Assume some interesting circuit-analysis algorithm
(B) Assume NEXP is in P/poly
... contradict the nondeterministic time hierarchy?
Conclude NTIME(2^n) is not in NTIME(o(2^n)), a contradiction.

What could this look like?
Every NTIME(2^n) function f has two parts:
On input x,
(1) Guess a witness y_x for x, of length O(2^n)
(2) Verify y_x is a witness in O(2^n) time.
To get a o(2^n)-time simulation,
we’d need to implement both parts in o(2^n) time.
(So, we need shorter witnesses, and we need faster verification.)

Idea: Try to use (B) to “speed up” part (1), and (A) to “speed up” part (2).
In part (1), we need an EWL for nondeterministic computation: small circuits encoding witnesses.

Such an EWL was proved by Impagliazzo-Kabanets-Wigderson in 2001.

[[[ Note: the below is an alternative way of putting it, omitted for this lecture
EWL for NEXP [IKW01]: NEXP in P/poly
=> "There are small circuits printing *accepting* computation histories of nondeterministic 2^n time TMs"
For every nondeterministic TM M running in O(2^n) time,
there is a poly-size circuit family {C_n} such that
for all x in {0,1}* such that M(x) accepts, there is some accepting computation path P such that
for all i,j, C_{|x|}(x,i,j) outputs the content of the j-th cells during the i-th step of path P. 
]]]

Notation:

For a circuit C with n inputs, let tt(C) in {0,1}^{2^n} be the *truth table of C*:
I.e. tt(C) = C(0^n)C(0^{n-1}1) C(0^{n-2}10) … C(1^n).

NEXP verifier: algorithm V(x,y) which takes y of length O(2^{|x|}) and runs in O(2^{|x|}) time.
These are the verifiers associated with NEXP problems.

EWL for NEXP [IKW01]: NEXP in P/poly
=> "There are small circuits printing *witnesses* for every NEXP verifier"
For every NEXP verifier V(x,y) and for all x,
If (Exists y_x of length 2^{k|x|})[V(x,y_x) accepts] 
Then (Exists poly(|x|)-size circuit C_x with k|x| inputs)[V(x,tt(C_x)) accepts].

In other words: the assumption implies that for every verifier,
 when there is a long witness y_x for the input x, 
then there is a "short" circuit C_x whose truth table is also a witness for x.

"Every yes-instance of every NEXP problem has a compressible witness"

We may prove this in a future lecture. 
For now, we’ll prove a much simpler (but weaker) EWL Lemma:

Weak EWL for NEXP: EXP^{NP} in P/poly
=> "There are small circuits printing *accepting* computation histories of nondeterministic 2^n time TMs"
For every NEXP verifier V(x,y) and all x,
If (Exists y)[V(x,y) accepts] Then (Exists poly(|x|)-size circuit C)[V(x,tt(C)) accepts].

Proof:
The following procedure can be computed in EXP^NP:

On input (x, i), use an NP oracle and binary search to find
   the lexicographically first witness y_x to x.
 [Keep querying the NP function:
  f(x,y’) = 1 iff there is a z such that V(x,y’z) accepts,
  Adding one bit at a time to y’ (start with y’=0, etc.)
  Query f for |y_x| times.]
  Output the i-th bit of y_x.

Assuming EXP^{NP} is in P/poly:
There is a poly(n)-size circuit D(x, i) which
outputs the i-th bit of the above y_x.
Now for any circuit C’, define the circuit E(i) := D(C’, i)
Then E has poly(n) size, and V(x,tt(E)) accepts!
QED

We can use the EWL for NEXP to greatly weaken the algorithm needed to get a lower bound.
It effectively says that if we improve over brute force for Circuit-SAT by some minor exponential amount, then NEXP is not in P/poly.

Thm [weak version]: If Circuit-SAT is in 2^{n/5}*2^{s^{o(1)}} time, then NEXP is not in P/poly.

Pf: Follow same strategy as before. Assume (A) there's a good SAT algorithm and (B) NEXP is in P/poly.
Let M be a 2^n-time nondeterministic multi-tape TM. We want to show that (A) and (B) imply M can be simulated in o(2^n) time, a contradiction.

Convert into a 2^{2n}-time one-tape TM.
EWL for NEXP and (B) imples there are circuits encoding accepting computation paths for M:
(the verifier here takes a computation history of M on x, and checks if it is valid and M on x accepts with it)
M(x) accepts <=>
(There is a circuit C of poly(|x|) size)
[C(x,2^{2n},1) is in an accept state]
& (Forall j)[C(x,0,j) is consistent with initial config of M(x)]
& (Forall i != 0,j)[C(x,i,j) is consistent with C(x,i-1,j-1),C(x,i-1,j),C(x,i-1,j+1)]

Idea: let (*) be the predicate *after* the existential quantifier.
In poly-time, we can reduce the conditions checked in (*) to one call to Circuit-SAT.

Construct a Circuit-SAT instance D:
- has description of C and x hard-coded
- has m=4n inputs: 2n bits to specify an index i, 2n bits to specify j.
Set D(i,j) = 1 <=> some condition on C in (*) is false with that i and j.
- Can make D have poly(n) size: on each i,j there are only O(1) calls to the circuit C.

Thus: D is UNSAT <=> for all i, j, the conditions on C are true.

So suppose we guess C, construct D in poly-time, then run Circuit-SAT alg on D.
Accept x <=> D is reported as UNSAT. 

(A) => This procedure takes time 2^{m/5}*2^{n^{o(1)}} <= 2^{4n/5+o(n)}.

So we have a nondeterministic algorithm for simulating M on inputs of length n: 
- guess a poly(n)-size circuit C,
- construct the circuit D with 4n inputs,
- run a SAT algorithm on D in 2^{4n/5+o(n)} time. 

Therefore NTIME(2^n) is in NTIME(2^{4n/5+o(n)}), which contradicts the nondeterministic time hierarchy!

QED

Using a lot more technical machinery
(a tighter reduction, which uses RAMs and does not go through one-tape TMs)
this theorem can be sharpened to:

Thm [W'10]: If Circuit-SAT is in 2^n/n^{omega(1)}*poly(s) time,
then NEXP is not in P/poly.

Note n^{omega(1)} just means any super-polynomial,
e.g. n^{log log log n} would work.

In fact, there is a generic connection between SAT for circuit classes and lower bounds for circuit classes:

Let C be a "natural" circuit class.
Think: arbitrary fan-in 2, or Boolean formulas, or AC0[m], or constant depth with any basis you like, as long as it can simulate unbounded OR and unbounded AND efficiently.

Thm [W'11]: If C-SAT is in 2^n/n^{omega(1)}*poly(s) time, 
then NEXP doesn't have poly-size C-circuits.

For AC0[m] circuits, we saw before that there *are* faster SAT algorithms:

Thm [W'11]: For all m,d there is an eps > 0 and a SAT algorithm that runs in 2^{n-n^{eps}} time on AC0[m] circuits of n inputs, 2^{n^{eps}} size, and d depth.

Cor: NEXP doesn't have poly-size AC0[m] circuits, for all m >= 2.

***
Weak Derandomization => Circuit Lower Bounds.

Perhaps you believe Circuit-SAT *is* really hard to solve, 
and brute-force can't even be improved by a super-polynomial factor.
It turns out that a Gap-SAT algorithm would suffice for NEXP lower bounds!

Thm [W'10]: If Gap-SAT is in 2^n/n^{omega(1)}*poly(s) time,
then NEXP is not in P/poly.

Thm [SW'13]: If Gap-C-SAT is in 2^n/n^{omega(1)}*poly(s) time, 
then NEXP doesn't have poly-size C-circuits.

These theorems are a very significant improvement, because Gap-SAT is widely believed to be in P!

I can't prove the above theorems in full here; they are too technical and would take too long.
I will prove a weaker version that only uses basic tools, found in (early parts of) Arora and Barak's textbook:

Gap-SAT Thm (also seen in [IKW'02]):
 If Gap-SAT on size-s circuits is in O(2^{s^{eps}}) time for all eps > 0, then NEXP is not in P/poly.

That is, sub-exponential time Gap-SAT algorithms imply the same desired lower bound.
This is still great, because Gap-SAT is believed to be in P anyway.
We can use IP=PSPACE to prove this!

Let's recall the definition of IP (Interactive Proofs)
Let P : {0,1}* -> {0,1} be a function. (P stands for Prover)
For a polynomial p(n), x in {0,1}^n, and r in {0,1}^{p(n)},
define the “interaction of P on input x with string r” I(P,x,r) as follows:
Define “response bits of P”
b_1 := P(x r_1), b_2 := P(x r_1 b_1 r_2), ..., b_{p(n)} := P(x r_1 b_1 r_2 b_2 ... r_{p(n)})
Then I(P,x,r) = r_1 b_1 ... r_{p(n)} b_{p(n)}.

Let r_1, ..., r_{p(n)} in {0,1}, uniform random.
Then intuitively, I is the “interaction of P with randomness”:
Over all 2^{p(n)} choices of the r_i, we get a distribution of (n+2p(n))-length strings, where some bits depend on the function P.

Def. f : {0,1}^* -> {0,1} is in IP if there’s a ptime verifier V(x,T) such that:
f(x) = 1 => there is a Prover response function P : {0,1}^{poly(n)} -> {0,1} such that
Pr_{r in {0,1}^{poly(n)}} [V(x,I(P,x,r)) accepts] = 1
f(x) = 0 => for all Prover functions P, Pr_r[V(x,I(P,x,r) accepts] < 1/10.

The fundamental theorem about IP is that it turns out to be EXACTLY PSPACE.
Thm [Shamir] IP = PSPACE.

Fact (follows from proof of IP=PSPACE) 
The "ideal" prover response function (when f(x) = 1) is computable in PSPACE.

Pf of Gap-SAT Thm:

 Let M be a 2^n-time nondeterministic TM. 
Assume NEXP is in P/poly.
NEXP is in P/poly => L(M) is in Sigma_2 P, the function computed by M is in Sigma_2 P.

Sigma_2 P is in PSPACE => 
There is an efficient *interactive proof* system for simulating M.
Let V be the poly-time verifier specifying this interactive proof system.

By the Fact, the "ideal" prover for this IP is computable in PSPACE: 
=> there is a poly-space algorithm, on every transcript, outputs the "ideal" prover's message.

NEXP in P/poly => PSPACE is in P/poly => the ideal prover itself has poly-size circuits: 
There is a poly-size family {C_n} such that,
given a transcript T of length t, 
circuit C_t(T) outputs the next bit of the ideal prover's message.

We can simulate M on x by the following procedure:
1. Guess circuits C_1,...,C_{poly(|x|)}, 
    where these C_t are intended to encode the ideal prover's strategy on transcripts of length t
2. Toss poly(n) coins c.
3. Simulate the IP for M(x) by the coins c; when you need messages from the prover, 
  query the appropriate C_t on the transcript built up so far. This constructs a whole transcript T.
4. Accept x <=> V accepts x on the T constructed.

Claim: The above is a Merlin-Arthur protocol simulating M on x!
Merlin's message: the circuits C_i. The rest is a randomized computation. 
By properties of the IP:
 M(x) accepts => there is a collection of C_t's such that Pr[V accepts] = 1.
 M(x) rejects => for all collections of C_t's, Pr[V accepts] < 1/2.

Now suppose we have a Gap-SAT algorithm that runs in 2^{s^{eps}} time on circuits of size s.

After guessing the poly(n)-size C_t's in step 1,
construct a circuit D with x and the C_t's hard-coded, 
takes in input c, 
and performs steps 3 and 4 (in polynomial time), but outputs 0 iff x is accepted in step 4.

Note D is a polynomial-size circuit.
 
Now observe:
M(x) accepts => there are C_t’s such that Pr_x[D(x) = 0] = 1, i.e. D is UNSAT
M(x) rejects => for all C_t’s, Pr_x[D(x) = 0] < 1/2
This is exactly the set of two promised cases where a Gap-SAT algorithm applies!

So instead of the above MA protocol, we can do the following:

1. Guess circuits C_1,...,C_{poly(|x|)}, 
    where these C_t are intended to encode the ideal prover's strategy on transcripts of length t
2. Construct D that takes coins c as input. Toss poly(n) coins c.
3. Run Gap-SAT algorithm on D.
4. Accept x <=> Gap-SAT algorithm says D is UNSAT.

We have a nondeterministic algorithm for simulating M on x which
- guesses poly(n) circuits C_t, then
- runs in 2^{n^{eps}} time for any desired eps > 0.

Since this works for every M, we have NTIME(2^n) in NTIME(2^{n^{eps}}), 
which contradicts the nondeterministic time hierarchy!
QED

By applying succinct PCPs for NEXP instead of IP=PSPACE, we can get a tighter result:

Thm [W'10]: For many C, if Gap-C-SAT is in 2^n/n^{omega(1)}*poly(s) (deterministic) time,
then NEXP doesn't have poly-size C circuits.