CS-540 Probabilistic Verification

 


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:


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


classes and notes

November 21
DATE
  SPEAKER
TITLE (link to talks)
Notes
September 5
Mario Szegedy
Abstract Proof Systems (Introduction)
hw1
September 10
Devendra Desai
Fourier transform over Abelian groups
I will be in Washington, in an NSF meeting.
September 12
Mario Szegedy
Polynomials over finite fields

September 17
Mario Szegedy
Codes I

September 19
Mario Szegedy
Codes II
hw2
September 24
Mario Szegedy
Bivariate testing
Reading: Polischuk and Spielman: Nearly linear size holographic proofs
September 26
Mario Szegedy
Class Canceled

October 1
Mario Szegedy
PCP theorem (traditional structure)

October 3
Mario Szegedy
PCP theorem (traditional structure) II

October 8
Mario Szegedy
Long code testing

October 10
Mario Szegedy
Dinur's Proof of the PCP theorem (readers)

October 15
Geetha
Dinur's proof of tha PCP theorem

October 17
Fengmin
Gap amplification lemma

October 22
Geetha, Brian
Dinur's proof (wrapping up)
Locally decodable codes I


October 24
Kooshiar Azimian,
Brian Thompson

Locally decodable Codes

October 29
Devendra Desai
Review of the material so far

October 31
Devendra Desai
tba
...
November 5
Mario Szegedy
Unique game conjecture

November 07
Mario szegedy
Unique game conjecture

November 12
Mario Szegedy
Majority stablest

November 14
TWO SPEAKERS
Unique game

November 19
TWO (NEW) SPEAKERS
unique game

Thanksgiving recess
Thanksgiving recess
Thanksgiving recess
November 26
Szegedy
unique game

November 28
Szegedy
unique game
...
December 3
Szegedy
unique game

December 05
invited
unique game

December 10
Szegedy
unique game

December 12
Szegedy
unique game

references