Sunday, May 01, 2005

a probabilistically checkable thesis

Spent the whole day preparing an (incomplete) summary of Ran Raz's paper on a quantum version of the PCP theorem (quant-ph/0504075), which turned into trying understand the papers that go into the classical PCP theorem (such as Arora-Sudan 97 and Raz-Safra 97). I'm now starting to appreciate why the PCP theorem is such an amazing result. (If you have no idea what the PCP theorem is, this article has a nice explanation without any math.)

Good stuff, except now it's midnight and the thesis is no farther along.

0 Comments:

Post a Comment

<< Home