Instructor: Mario Szegedy,
szegedy@cs,
446 Hill Center, Tel. 445-4184
TA: Devendra Desai, devdesai@cs, 203 Hill Center, Tel. 445-2001 Ext. 9542
Classes are Mondays-Wednesdays, 1:40-3:00pm, 254 Hill
Office hours: Wednesdays, Fridays, (by appointment).
Requirements:
Probabilistic verification started to develop in the mid eighties
and now it is central to complexity theory and combinatorial optimization.
The theory requires significant machinery from Fourier analysis,
linear codes and polynomials over finite fields,
and we provide this background first.
Then we will prove the PCP theorem
following the outline of Irit Dinur, we prove
Hastad's sharp inapproximaility results
and also spend a lecture on locally decodable codes (the type
of code that occurs in PCP theory and elsewhere).
In the third part of the course we give
the current most elegant proof of the famous parallel repetition
theorem of Raz (the new proof is due to Holenstein), and discuss the unique
game conjecture and its consequences in great details.
references