This week I started teaching the PCP theorem: Every language in NP has
a proof that can be probabilistically checked with only O(log n)
random coins and a constant number of queries. One graduate student
asked me which came first, the PCP theorem or the connection to
hardness of approximation. That seemed like a strange question; after
all why would so much effort be put into reducing parameters like
number of random coins or queries unless there was some application
behind it. But then again, so much emphasis is now in the literature
on these parameters that he probably thought these were always the
parameters people cared about the most.

To put the record straight: Feige, Goldwasser, Lovász, Safra and Szegedy made the connection
between the interactive proof literature and approximation. Arora and
Safra showed the importance of reducing random coins and queries and
proved a weaker version of the PCP theorem. The theorem in the above
form was proved by Arora, Lund, Motwani, Sudan and Szegedy.

I have been teaching off the notes of Madhu Sudan from a short course
he taught on the PCP theorem. The notes don't go through every detail,
but they give one of the better expositions of what is still quite a
complex proof.

## No comments:

## Post a Comment