You are not logged in | Log in

Probalistically Checkable Proofs and approximation hardness

Speaker(s)
Anna Niewiarowska
Date
May 9, 2007, 2:15 p.m.
Room
room 5870
Seminar
Seminar Automata Theory

The PCP theorem states that for each NP language there is a verifier that checks membership proofs probabilistically, using only logaritmic number of random bits and reading constant number of proof bits. I will show that many approximation hardness results are consequences of that theorem. I will also show the idea of the proof of the PCP theorem.