Lecture 30

The Final Lecture.

NEXP not in ACC⁰, part II.

Scribe Notes by Tom Hayden

Lecture 29

Final Exam posted on assignments page.

NEXP not in ACC<sup>0


Scribe Notes by Manolis Pountourakis</sup>

Non-Uniform ACC Circuit Lower Bounds by Ryan Williams

Lecture 28

S₂^P

Scribe Notes by Michele Budinich

• Symmetric Alternation Captures BPP by Russell and Sundaram
• S₂^P in ZPP^NP by Cai
• On the Complexity of Succinct Zero-Sum Games by Fortnow, Impagliazzo, Kabanets and Umans

Lecture 27

PCP Post Mortem

Scribe Notes by  Tom Hayden

Approximation Classes, Parallel Repetition, Uniques Games, Max Cut

• Uniques Games Survey by Subhash Khot
• Semidefinite Programming for Max Cut by Goemans and Williamson
• Two-query PCP with subconstant error by Ran and Moshkovitz

Lecture 26

Linearity Testing to end the PCP proof.

Lecture 25

PCP - Alphabet Reduction Part I

Scribe Notes by Darrell Hoy

Lecture 24

PCP Gap Amplification Continued