Fall 2007 - Probabilistically Checkable Proofs (236603)

Scribe notes and exercises [PDF, PS]

A lazy instructor wishes to write an exam such that checking it will be easy. The lazy instructor is not willing to read more than 20 (randomly selected) bits from each returned exam, irrespective of its length. The exams should be graded correctly, because every erroneously graded exam will cause the student who wrote it to appeal, costing our poor instructor extra time and agony.

Can our instructor fulfill all these demands? Surprisingly, the answer is yes. This can be achieved if the students are told to write their exams in a so-called "probabilistically checkable" format. This magical proof-format will be the focus of our course. We shall learn how to construct, check and analyze probabilistically checkable proofs. Our working tools come from linear algebra, combinatorics, probablity, harmonic analysis and the theory of error correcting codes.

Main topics:

Tentative Schedule