Lectures

Following is an outline of lectures given along with references and links to additional reading.

\( \def\SAT{\mathsf{SAT}} \def\USAT{\mathsf{USAT}} \def\DTIME{\mathsf{DTIME}} \def\DTIME{\mathsf{DTIME}} \def\NTIME{\mathsf{NTIME}} \def\DSPACE{\mathsf{DSPACE}} \def\NSPACE{\mathsf{NSPACE}} \def\poly{\mathsf{poly}} \def\P{\mathsf{P}} \def\NP{\mathsf{NP}} \def\co{\mathsf{co}} \def\coNP{\mathsf{coNP}} \def\L{\mathsf{L}} \def\NL{\mathsf{NL}} \def\PSPACE{\mathsf{PSPACE}} \def\NPSPACE{\mathsf{NPSPACE}} \def\EXP{\mathsf{EXP}} \def\E{\mathsf{E}} \def\NEXP{\mathsf{NEXP}} \def\RP{\mathsf{RP}} \def\coRP{\mathsf{coRP}} \def\ZPP{\mathsf{ZPP}} \def\PP{\mathsf{PP}} \def\FP{\mathsf{FP}} \def\sharpP{\#\mathsf{P}} \def\BPP{\mathsf{BPP}} \def\BP{\mathsf{BP}} \def\AC{\mathsf{AC}} \def\NC{\mathsf{NC}} \def\SC{\mathsf{SC}} \def\RL{\mathsf{RL}} \def\BPL{\mathsf{BPL}} \def\ZPL{\mathsf{ZPL}} \def\PAL{\rm PAL} \)

Lec 1 (25 Aug, Thu) : Course plan and broad overview of the complexity landscape. Administrative info. Computation and why study it.

^{Reading : Kozen Lec 1. For a broad perspective of the theory of computing, see Chapter 20 of this very nice book.}

Lec 2 (30 Aug, Tue) : Randomized classes $\RP$, properties, error amplification

^{Reading : Kozen Lec 13, Arora-Barak Chap. 7}

Lec 3 (01 Sep, Thu) : DeMillo-Lipton-Schwartz-Zippel lemma and applications

^{Reading : Arora-Barak sec 7.2}

Lec 4 (06 Sep, Tue) : Polynomial identity testing. Examples - Bipartite perfect matching, Primality testing. Primality testing in $\co\RP$. Classes $\ZPP$, $\PP$. Containments

^{Reading : Arora-Barak sec 7.3, sec 7.4, sec 7.5}

Lec 5 (13 Sep, Tue) : Error amplification in BPP, Non-uniform models - PSIZE, $\P/\poly$, Adleman's theorem

^{Reading : Arora-Barak sec 7.5, sec 6.1}

Lec 6 (15 Sep, Thu) : Sipser-Gacs theorem

^{Reading : Kozen Lec 14}

Lec 7 (20 Sep, Tue) : Karp-Lipton hierarchy collapse

^{Reading : Arora-Barak sec 6.3, 6.4}

Lec 8 (22 Sep, Thu) : Cancelled. To be compensated.

^{Reading :}

Lec 9 (27 Sep, Tue) : Randomness in space - $\RL, \BPL, \ZPL$. Random walk on regular undirected graphs with self loops.

^{Reading : Arora-Barak sec 7.7, sec 21.1}

Lec 10 (29 Sep, Thu) : Convergence of the random walk and relation to second largest eigenvalue.

^{Reading : Arora-Barak sec 21.1}

Lec () (04 Oct, Tue) : Recess break

Lec 11 (06 Oct, Thu) : Bounding the second largest eigenvalue away from $1$. Completed proof of $UREACH \in \RL$.

^{Reading : Arora-Barak sec 21.1}

Lec 12 (11 Oct, Tue) : Berman Hartmanis conjecture and Mahaney's theorem. Applications.

^{Reading : Kozen Lec 29}

Lec 13 (13 Oct, Thu) : Counting complexity. Motivation and examples. The classes $\FP$, $\#\P$. Counting versus decision problems. $\#\mathsf{CYCLE} \in \FP$ implies $\P=\NP$.

^{Reading : Arora-Barak sec 17.1, 17.2}

Lec 14 (18 Oct, Tue) : Definition of $\#\P$-completeness, parsimonious reductions. $\#\SAT$ is $\#\P$-complete. Permanent over $\{0,1\}$ matrices and it combinatorial interpretation via counting perfect matchings.

^{Reading : Arora-Barak sec 17,3}

Lec () (20 Oct, Thu) : Class cancelled. To be compensated.

Lec () (25 Oct, Tue) : Class cancelled. To be compensated.

Lec 15 (27 Oct, Thu) : Computing Permanent over integer matrices. Combinatorial interpretation via cycle covers. Chain of reductions from (1) $\#\SAT$ to $\#\mathsf{3SAT}$ (2) $\#\mathsf{3SAT}$ to $Perm_{\{-1,0,1\}}$, (3) $Perm_{\{-1,0,1\}}$ to $Perm_{\{0,1,\ldots,n\}}$ and (4) $Perm_{\{0,1,\ldots,n\}}$ to $Perm_{\{0,1\}}$. Shows $\#\P$-hardness of Permanent.

^{Reading : Class notes.}

Lec () (01 Nov, Tue) : Class cancelled. To be compensated.

Lec 16 (03 Nov, Thu) : Parsimonious reduction from $\#\mathsf{3SAT}$ to $Perm_{\{-1,0,1\}}$ - details of variable, clause and equality gadgets

^{Reading : Section 3 of this paper and class notes.}

Lec 17 (04 Nov, Fri) : (Compensatory, continued from previous lecture) Argued correctness.

^{Reading : Section 3 of this paper and class notes.}

Lec () (08 Nov, Tue) : Holiday due to Guru Nanak Jayanti.

Lec 18 (10 Nov, Thu) : Toda's Theorem. Statement and overview of proof. Introduction to $\USAT$, $\oplus \SAT$ and randomized reductions. Naive approaches and why they fail.

^{Reading : Arora-Barak, sec 17.4}

Lec 19 (11 Nov, Fri) : (Compensatory) Valiant-Vazirani Lemma. Proof of randomized reduction from $\SAT$ to $\USAT$ assuming pairwise independent hash family. Construction of pairwise independent hash family.

^{Reading : Arora-Barak, sec 17.4, class notes}

Lec 20 (15 Nov, Tue) : Amplifying the success probability of the randomized reduction. Showing $\SAT$, $\overline{\SAT}$ randomly reduces to $\oplus\SAT$ with high probability. Overview of $\Sigma_2^P\SAT$ reduces to $\oplus\SAT$.

^{Reading : Arora-Barak, sec 17.4. Also see this notes.}

Lec 21 (17 Nov, Thu) : Randomized reduction for $\Sigma_2^p$-$\SAT$. Derandomization argument. Completed the proof of Toda's theorem.

^{Reading : Arora-Barak, sec 17.4.}

Lec 22 (18 Nov, Fri) : (Compensatory) Mid Quiz

^{Reading :}

Lec () (22 Nov, Tue) : Class cancelled

Lec 23 (24 Nov, Thu) : Introduction to Arthur Merlin protocols. Connection to randomized reductions - $\BP\cdot \NP$. Overview of GI is NP-complete implies PH collapses.

^{Reading : Arora-Barak, sec 8.2}

Lec 24 (29 Nov, Tue) : Details of $\overline{\SAT}$ in $\BP\cdot\NP$ implies PH collapses. Overview and ideas for showing GNI has two round Arthur Merlin protocols. Course wrap-up.

^{Reading : See this write up on Goldwasser-Sipser protocol}