# CS6840 Modern Complexity Theory

## Feb - May 2021

The lecture videos and the notes written during the lectures are available below.

- Week 1
- Administrative details about the course; Recap from last semester - probabilistic complexity classes; Complexity of counting - the classes PP and #P; Notion of #P-completeness and parsimonious reductions; Perfect matchings, cycle covers and permanent of matrices.

- Week 2
- Valiant’s theorem - counting perfect matchings in bipartite graphs is #P-complete. Toda’s theorem - BP and parity operators and their properties; Isolation lemma and its proof.

- Week 3
- Toda’s theorem - Randomized reduction from NP to \(\oplus\) P; relativizing the reduction to PH; Derandomizing the reduction - Modulus amplifying polynomials; Boolean circuits and lower bounds; Shannon’s lower bound and Lupanov’s upper bound.

- Week 4
- Uniform circuit families; P-uniform P/poly is P; NC and AC hierarchy; Examples of functions in NC and AC; P vs NC question and P-completeness; Lower bounds: Restrictions and Gate elimination - Schnorr’s lower bound; Random restrictions and shrinkage - Subbotovskaya’s lower bound; Lower bounds for parity - decision trees and the switching lemma.
- Videos: Feb 22, Feb 24, Feb 25
- References: [AB] - Chapters 6; Rossman’s notes; Kopparty’s notes
- Scribbles: Feb 22, Feb 24, Feb 25

- Week 5
- Lower bounds for parity - decision trees and the switching lemma; Proof of the switching lemma.
- Videos: Mar 1, Mar 4
- References: Rossman’s notes; Kopparty’s notes; Switching Lemma Primer
- Scribbles: Mar 1, Mar 4

- Week 6
- Majority in \(NC^1\); Parity constant-depth reduces to Majority; Lower bound for \(AC^0(\oplus)\) - Razborov-Smolensky technique.

- Week 7
- Lower bound for \(AC^0(MOD_{p^k})\) - Razborov-Smolensky technique; Hardness vs Randomness - Definition of PRGs; Derandomization using PRGs; PRGs and unpredictability.
- Videos: (will be updated)
- References: Smolensky’s paper and Filmus’ exposition; [AB] - Chapter 20
- Scribbles: Mar 15 (will be uploaded soon), Mar 17 and 18

- Week 8
- PRGs and unpredictability; Hardness vs Randomness - the Nisan-Wigderson generator; Hardness amplification: Yao’s XOR lemma - from mild to strong hardness; Impagliazzo’s hardcore lemma; Brief outline of locally decodable codes - from worst-case hardness to mildly average-case hardness.
- Videos: (will be updated)
- References: [AB] - Chapters 19 and 20
- Scribbles: (will be uploaded soon)

- Week 9
- Mid-semester break

- Week 10
- Interactive proofs - private coins and public coins; Arthur-Merlin games; Interactive proof for graph non-isomorphism; Set lower bound protocol - AM protocol for graph non-isomorphism; properties of the classes AM and MA.

- Week 11
- Simulating the optimal prover in PSPACE; Permanent in IP: LFKN protocol; IP = PSPACE: Using self-reducibility, arithmetization and linearization.
- Videos: (link sent on the course mailing list)
- References: [AB] - Chapter 8, Babai’s exposition
- Scribbles: (will be uploaded soon)

- Week 12
- IP=PSPACE: final protocol; Proof verification view of interactive proofs; MIP = PCP(\(n^c, n^c\)); Statement of the PCP theorem; PCP theorem and inapproximability.
- References: [AB] - Chapters 8, 11

- Week 13
- Example of a PCP for NP - NP \(\subseteq\) PCP\((n^c, O(1))\); Derandomization implies circuit lower bounds - Kabanets-Impagliazzo theorem; IKW theorem - hard witnesses and derandomization; From SAT algorithms to circuit lower bounds - statement of Williams’ theorem.
- References: [AB] - Chapters 11, 22; Gil Cohen’s lecture notes
- Additional reading:
- Limits of Approximation Algorithms - PCPs and Unique Games: Lecture notes
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds - Ryan Williams

- Week 14
- From SAT algorithms to circuit lower bounds - statement and proof of Williams’ theorem; Succinct certificates and verification; Wrap-up of the course.
- References: Gil Cohen’s lecture notes
- Additional reading:
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds - Ryan Williams
- Non-Uniform ACC Circuit Lower Bounds - Ryan Williams