Estonian Winter Schools in Computer Science    
Eesti arvutiteaduse talvekoolid
EWSCS 2003
EATTK 2003

8th Estonian Winter School in Computer Science (EWSCS)
VIII Eesti Arvutiteaduse Talvekool (EATTK)

Palmse, Estonia
March 2 - 7, 2003

Johan Håstad

Kungl Tekniska Högskolan, Stockholm

Probabilistically Checkable Proofs and Inapproximability


A traditional NP-proof of a statement is verified by a polynomial time deterministic verifier that always accepts a correct proof and never accepts a proof of an incorrect statement. The verifier typically would read the entire proof.

A Probabilistically Checkable Proof (or simply PCP) is verified by a polynomial time probabilistic verifier that only reads a very small part of the proof. The celebrated PCP-theorem says that any NP-statement admits a PCP where a correct proof is always accepted and where the verifier only reads a number of bits that is independent of the size of the statement being proved. A proof of an incorrect statement is accepted with probability at most a half.

Apart from being a mathematically appealing concept, PCPs (with proper parameters) are extremely useful for proving inapproximability results for NP-hard optimization problems.

The aim of the first part of the course is to give an outline and part of the proof of the PCP-theorem. The second part of the course will give applications to inapproximability of some basic NP-hard optimization problems.

Course materials

About the Lecturer:


Modified Monday, Oct 12, 2015 at 17:19 EEST+0300 by