CS-596, 2011 Probabilistic Verification

Instructor: Mario Szegedy, szegedy@cs, 446 Hill Center, Tel. 445-2001 Ext.4184

TA: Devendra Desai, devdesai@cs, 203 Hill Center, Tel. 445-2001 Ext. 9542

Classes are Mondays-Wednesdays, 1:40-3:00pm, 120 Hill

Office hours: by appointment

Requirements:

• The homework is to read your class notes.
• Be present in the class
• Be active in class. Some might choose to give a little presentation.

course description

Probabilistic verification started to develop in the mid eighties and now it is central to complexity theory and combinatorial optimization.

The theory requires machinery from Fourier analysis, linear codes and polynomials over finite fields. We try to minimize necessary background.

We shall prove the clique in-approximability result of FGLSS, the PCP theorem following the outline of Irit Dinur, we prove Hastad's sharp inapproximaility results, we mention the Unique Games Conjecture and its consequences.

We shall adapt our speed to the class.

classes and notes

references

• Arora's thesis
• Hastad's articles (Some optimal inapproximability results, etc.)
• Irit Dinur's new poof of the PCP theorem
• Holenstein new proof for the parallel repetition theorem
• Subbash Khot's articles (On the power of 2 prover 1 round games, etc.)
• The solution of the majority stablest conjecture