Probabilistic checking of proofs: a new characterization of NP
Interactive proofs and the hardness of approximating cliques
Journal of the ACM
Shafi Goldwasser
Sanjeev Arora
László Lovász
Mario Szegedy
Uriel Feige
Bypassing UGC from Some Optimal Geometric Inapproximability Results
Guest column