A Mini-Course on Probabilisitcally Checkable Proofs
Lecture notes available here.
You are asked to grade a student’s homework assignment. If instead of reading the student’s entire solution you only checked a few random sentences and gave an A+ if they made sense, your boss would be furious: surely, you had no way of knowing that the solution was perfect from a superficial glance. It turns out that any homework assignment can be solved in a special form that allows for such “lazy” checking.
This concept is known as a Probabilistically Checkable Proof (PCP) and is one of the most important advances in modern complexity theory. We will formally introduce the notions behind this “laziness” and examine, at a glance, a key result in its development and understanding. Our journey will take us through the field of property testing and Fourier analysis of Boolean functions (no prior knowledge of these is needed!).
Familiarity with the class NP and with NP-completeness is recommended. We will also use some linear algebra and basic probability.