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


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

This is our first note