[Lowerbounds, Upperbounds]

Check this out…. a new 10 page (only!) proof to the PCP theorem due to Irit Dinur:
http://eccc.uni-trier.de/eccc-reports/2005/TR05-046/index.html

Finally I can hope to try to understand the theorem! And supposedly it uses a purely combinatorial amplification lemma.

Jason Hartline
Microsoft
3:30PM, Friday 2005-04-22
4625 Wean Hall

Derandomization of Auctions

ABSTRACT:
Read the rest of this entry »