CIDEC    
ÜIK
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

NADA
Kungl Tekniska Högskolan, Stockholm

Probabilistically Checkable Proofs and Inapproximability

Abstract

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:

URL: http://www.nada.kth.se/~johanh/

http://www.cs.ioc.ee/yik/schools/win2003/

Modified Monday, Oct 12, 2015 at 17:19 EEST+0300 by monika@cs.ioc.ee