A PCP characterization of NP with optimal amortized query complexity.

Alex Samorodnitsky, Luca Trevisan

Browse the full STOC paper archive.