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

Lecture 23

PCP Continued. Transformation to reduce degree and turn graph into an expander.

Lecture 22

PCP Theorem Continued: Gap Amplification

Scribe Notes by Arefin Huq

• Expander Survey by Hoory, Linial and Wigderson. 

Lecture 21

PCP Theorem: The Proof Begins

Scribe Notes by Arefin Huq

• On Dinur's proof of the PCP theorem by Radhakrishnan and Sudan

Breaking News: Ryan Williams proves NEXP not in ACC⁰

Lecture 20

The PCP Theorem Part I

Assignment 4 posted and due Wednesday, November 17.

Scribe Notes by Manolis Pountourakis.

• The PCP theorem by gap amplification by Irit Dinur
• Proof verification and the hardness of approximation problems by Arora, Lund, Motwani, Sudan and Szegedy (the original PCP theorem)

Lecture 19

IP = PSPACE

Scribe Notes by Darrell Hoy

JACM Issue with all three IP=PSPACE papers

Lecture 18

Toda's Theorem

Scribe Notes by Nima Haghpanah

A Simple Proof of Toda's Theorem