Nie jesteś zalogowany | Zaloguj się

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.