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.

---