MIT Department of Electrical Engineering & Computer Science

EECS Spring 1997 Catalogue Supplement

6.966 Recent Results on PCP and Approximation (G)

W 4-6, NE43 Third Floor Conference Room
Prof. Shafrira Goldwasser, NE43-332, x5914
3-0-3

This is an advanced graduate complexity seminar. The plan is to cover some of the basics of this area initially, and then spend most of the time discussing recent results which will appear, or which have recently appeared, in conferences. Lectures will be given by faculty, outside speakers, and students.

Topics (each topic corresponds to at least one lecture):

IP definitions, IP = Pspace

MIP, PCP definitions, MIP = PCP

PCP (parameters) definitions, connection of "NP in PCP (parameters)," to getting NP-completeness results for approximation problems such as 3-SAT problem, clique problem, set cover problem. What values of "parameters" yield strong hardness results.

Key ideas in the simplest (so far) known proof for "NP in PCP (parameters):" codes, low degree, composition, parallelization, sum checks. An outline of the proof using ideas.

New low error MIP protocols (by Safra and Raz)

New low degree testing (by Arora and Sudan)

New and strong inapproximability results on clique and 3-SAT (by Hastad)

Tools in the proof: pairwise independence, saving randomness using expander walks, parallelizations, consistency checking