CIDEC ÜIK |
Estonian Winter Schools in Computer Science Eesti arvutiteaduse talvekoolid |
EWSCS 2003 EATTK 2003 |

VIII Eesti Arvutiteaduse Talvekool (EATTK)

March 2 - 7, 2003

NADA

Kungl Tekniska Högskolan, Stockholm

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.

M. Sudan. Probabilistically checkable proofs. Course notes for Graduate Summer School within Inst. for Adv. Study/Park City Math. Inst. 2000 Summer Session on Computational Complexity Theory (Princeton, NJ, July/Aug. 2000). [ps]

J. Håstad. On linear equations and satisfiability. Notes (based on the paper Some optimal inapproximability results), 2003. [ps]

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

Modified Tuesday, Jun 02, 2020 at 13:58 EEST+0300 by monika@cs.ioc.ee