Probalistically Checkable Proofs and approximation hardness

Prelegent(ci)

Anna Niewiarowska

Termin

9 maja 2007 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---