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
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.