Lecture 28

Today we talked about barriers to proving $P \neq NP$ and other complexity-theory results: specifically, the "relativization" barrier introduced by Baker-Gill-Solovay, and the "natural proofs" barrier introduced by Razborov-Rudich.

We also talked about results that evade them. For example, the Hopcroft-Paul-Valiant Theorem, $TIME[f(n)] \neq SPACE[f(n)]$, and the Paul-Pippenger-Szemeredi-Trotter Theorem, $DTIME[n] \neq NTIME[n]$, do not relativize. Nor do they algebrize, according to the Aaronson-Wigderson notion. (At least, my opinion is that the notion of relativizing/algebrizing makes sense for these theorems, and in this sense they do not relativ/algebrize.)

As for natural proofs, we discussed how proofs by diagonalization do not seem to naturalize, and we mentioned explicit circuit lower bound which are by diagonalization; for example, Kannan's result that $\Sigma_4$ not in $SIZE(n^{1000})$.

Finally, we mentioned some theorems that neither relativize nor (seem to) naturalize: for example, Vinodchandran's Theorem that $PP$ not in $SIZE(n^{1000})$, and Santhanam's improvement of this to an explicit promise problem in $MA$ which isn't in $SIZE(n^{1000})$.

Lecture 27

In this lecture we covered Reingold's Theorem, SL = L; i.e., undirected connectivity can be solved in log space. Here are my abridged notes on actually doing Reingold's algorithm in log-space. It's not a full proof, just a "proof by example" -- but I hope it's nevertheless clearer than a hand-wave.

For the Martin-Randall Theorem, you can consult the original Martin-Randall paper. There is a clearer proof -- but of a much more general theorem -- in a paper by Jerrum, Son, Tetali, and Vigoda. It's still not the clearest thing. If I get time I will try to write up a stripped-down, simplified version of the proof. You can also consult the Arora-Barak book for a proof of a weaker but still sufficient result: $\epsilon(G r H) \geq \Omega(\epsilon(G) \epsilon(H)^2)$. Note that it is okay to have the square on $\epsilon(H)$ here since it's an absolute constant anyway -- but it would not help if the square were on $\epsilon(G)$.

Lecture 26

Today we covered...

Proof Complexity and the NP vs. coNP problem. The "Resolution" proof system with the resolution rule ($C \vee x$, $C \vee \overline{x}$ $\vdash$ $C \vee C'$) and the weakening rule ($C \vdash C \vee x$). Completeness of Resolution with proof sketch. Various contradictions (tautologies, in fact): Pigeonhole Principle, Tseitin Tautologies, Random 3-CNF. Treelike Resolution. Resolution width. Short Proofs Are Narrow Theorem, proved for Treelike Resolution. Ben-Sasson & Wigderson Theorem: Unsatisfiable $k$-CNFs with "expansion" require wide Resolution proofs.


By the way, the question came up as to separating Treelike Resolution from General Resolution. A very strong result was proved for this problem by Ben-Sasson, Impagliazzo, and Wigderson: There is a natural family of contradictions with $n$ variables and $O(n)$ clauses, which have Resolution refutations of length $O(n)$ but requires Treelike Resolution refutations of length $2^{\Omega(n / \log n)}$.

The contradictions here are based on "pebbling" expander graphs; more specifically, the results in an old paper of Paul, Tarjan, and Celoni.

Lecture 25

Today Eric gave an introduction to Property Testing. Among other things, we covered the BLR Linearity Test with the Bellare-Coppersmith-Håstad-Kiwi-Sudan proof using Fourier analysis.

Lecture 24

In today's class we covered many of the gory details of expander graphs. I didn't quite get a chance to finish the last details, so there are the notes.

Lecture 23

Today we finished the proof of the IKW Theorem. We also showed fhe Kabanets-Impagliazzo Theorem: derandomizing Arithmetic Circuit Identity Testing implies $NEXP$ not in $P/poly$ or Permanent not in $AlgP/poly$ or both.

We then moved on to the definition of expander graphs, the definition of strongly explicit graph families, and saw the Lubotsky-Phillips-Sarnak and Margulis-Gabber-Galil expander families.

Lecture 22

In this lecture we covered "derandomization implies circuit lower bounds" topics. In particular, we saw:

Kannan's Theorem, $\Sigma_2$ doesn't have fixed-polynomial size circuits.

The Babai-Fortnow-Lund Theorem, $EXP \subseteq P/poly \Rightarrow EXP = MA$, and its consequences: $MA$-$EXP$ does not have polynomial size circuits, derandomizing $MA$ to $NP$ implies showing $NEXP$ does not have polynomial size circuits.

Most of the Impagliazzo-Kabanets-Wigderson Theorem, $NEXP \subseteq P/poly \Rightarrow NEXP = EXP$ (and indeed $NEXP = MA$), along with Kabanets's "easy witness method". The remainder will be proved next time.

Lecture 21

Today we saw the completion of Sudan-Trevisan-Vadhan's proof of the Impagliazzo-Wigderson Theorem: if there is a positive $\epsilon > 0$ such that $E$ contains a language not in $SIZE(2^{\epsilon n})$, then $P = BPP$. This included Sudan's algorithm for list-decoding Reed-Solomon codes.

Lecture 20

Today we covered...

Reed-Muller code review. Local decoding with "random lines". Code concatenation. Beginning Sudan-Trevisan-Vadhan's hardness amplification.

Lecture 19

Today we covered...

Completion of proof of Impagliazzo's Hard-Core Set Theorem, Yao's XOR Lemma. Intro to error-correcting codes, list-decodable codes, locally decodable codes. Reed-Solomon codes, Hadamard codes, Reed-Muller codes. Connection between local list-decoding and hardness amplification.

Lecture 18

Today we covered: Hardness vs. randomness corollaries of Nisan-Wigderson; Impagliazzo-Wigderson Theorem ($f \in \mathsf{E}$ requiring circuits of size $2^{\epsilon n}$ implies $\mathsf{P} = \mathsf{BPP}$); Hardness Amplification , $1 - 1/\mathrm{poly}(n)$ hardness to $1/2 + 1/\mathrm{poly}(n)$ hardness, with the XOR Lemma; Impagliazzo's proof via the Hard-Core Set Theorem (with Nisan's proof via the Minimax Theorem).

Lecture 17

In this lecture we covered the Nisan-Wigderson Generator, which connects hardness to randomness. In the course of proving it we also saw designs and the Yao Next-Bit Predictor Theorem, which uses the "hybrid method".

Lecture 16

In this lecture we covered Nisan's pseudorandom generator for log space.

One thing I had to rush over at the end was the actual definition of the generator, along with its seed length!

Here is an official inductive definition of the generator: Let $h_1, ... h_{\lg n} : \{0,1\}^k \to \{0,1\}^k$ be functions. We define $G_t : \{0,1\}^k \to \{0,1\}^{2^t k}$ inductively by $G_0(x) = x$, $G_{t}(x) = (G_{t-1}(x), G_{t-1}(h_t(x)))$.

Finally, Nisan's generator $G$ maps $\langle x, h_1, ... h_{\lg n} \rangle$ into $G_{\lg n}(x)$. Here the $h_i$'s are the "descriptions" of the hash functions.

Recall that we are using the simple "$a \circ x + b$" pairwise independent hash family; the "description" of such a function is just the $2k$-bit string $\langle a, b\rangle$. Conveniently, choosing this description uniformly at random coincides with choosing $h \sim \mathcal{H}_k$ uniformly at random.

So finally, the seed length is $\ell = k + (\lg n)(2k)$. Since $k = O(\log S)$, this is indeed $O(S \log n)$ seed-length, as claimed. The number of output bits is in fact $nk = O(n \log S)$ (which is, as we noted, slightly more than we need).

Lecture 15

In this lecture we finished the proof of the Switching Lemma and showed how it implied Håstad's Theorem: Computing Parity by depth-$k$ circuits (unbounded fan-in) requires size $2^{\Omega(n^{1/(k-1)})}$.

We then stated and sketched the proof of the Linial-Mansour-Nisan (LMN) Theorem: If $f$ is computed by depth-$k$, size-$S$ circuits, then there is a multilinear real polynomial $p$ of degree at most $t = O(\log(S/\epsilon))^{k}$ which approximates $f$ in the following sense:

E${}_{x}[(f(x_1, ..., x_n) - p(x_1, ..., x_n))^2] \leq \epsilon$,

where $x = (x_1, ... x_n)$ is a uniformly random string.

By the way, Håstad subsequently slightly sharpened this; he improved $t$ to

$O(\log(S/\epsilon))^{k-1} \cdot min\{\log S, \log (1/\epsilon)\}$.

Lecture 14

In this class we reviewed DNF/CNF size and width decision tree size and depth. We then began the proof of the Switching Lemma, which we will finish next time. If you want to read up on it, we are following Paul Beame's exposition.

Also, Homework #4 is out. It is due in 3 weeks, after which we will have the midterm. This midterm will occupy either 5 or 7 days.

Lecture 13

Today we covered: Parity has unbounded fan-in circuits of depth-$d$ size-$2^{\Theta(n^{1/(d-1)})}$. Hastad's Theorem statement: This is also a lower bound for constant $d$. Proof in the case $d = 2$ (CNF, DNF). Razborov-Smolensky proof with $1/(4d)$ rather than $1/(d-1)$. Its main tool: For any $k$, $\epsilon$, there is a probability distribution on $k$-variable polynomials of degree $O(\log k \log(1/\epsilon))$ such that for every $k$-bit input $x$ we have $\Pr[p(x) = OR(x)] \geq 1 - \epsilon$ when $p$ is chosen from the distribution. Expanding functions $f : \{-1,1\}^n \to \mathbb{R}$ in the Fourier basis.

Lecture 12

Today we covered: Definitions of $AM[k]$ and $MA[k]$; $AM[k]$ and $MA[k]$ unchanged if perfect completeness required (statement); $MA = MA[2] \subseteq AM[2] = AM$; $AM[k] = AM[2]$ for all constant $k$; indeed, $AM[4r] \subseteq AM[2r+1]$ for any $r = r(n)$; $AM \subseteq \Pi_2$; Boppana-Hastad-Zachos Theorem, $coNP \subseteq AM \Rightarrow PH = AM$; Graph-Non-Isomorphism is not $NP$-complete unless the hierarchy collapses to $\Simga_2$; Goldwasser-Sipser Theorem, $k$-round private-coin interactive proofs are doable with $(k+10)$-round public-coin interactive proofs, hence $AM$ is unchanged if public coins are required; set size lower bound protocol in public coins $AM$.

Lecture 11

In Lecture 11, we covered:

Telling coke and pepsi apart: Interactive protocol for Graph nonisomorphism;
Interactive proof for Counting-SAT (and so PH is a subset of IP);
The precise power of interaction: IP = PSPACE ;
Perfect completeness and public coins don't change power of IP.

Graded problem set 1 was handed back.

Lecture 10

Topics covered in Lecture 10:

Barrington's theorem: NC^1 has constant width branching programs (Ben-Or & Cleve's proof which showed width 7)
Lipton-Viglas theorem: SAT can't be solved in simultaneous n^{o(1)} space and n^{1.41} time.
Comments on relativization and limits of diagonalization
Introduction to Interactive proofs

Lecture 9

Topics covered in Lecture 9:

Randomized space: $RL \subseteq BPL \subseteq L^{3/2}$ (Saks-Zhou Theorem), USTCON $\in RL$. Circuits (as parallel computation): $NC$ vs. $P$, $NC^0$, $NC^1 \subseteq L \subseteq NL \subseteq NC^2$, matrix multiplication in $NC^1$, nonuniform $NC^1 = $ poly-size formulas. Branching programs: non-uniform $L = $ poly-size branching programs, small-width branching programs, statement of Barrington's Theorem (nonuniform $NC^1 = $ constant-width poly-size branching programs).