Articles under category:
PCP
Vol 18, Article 12 (pp 1-25)
From Local to Robust Testing via Agreement Testing
by Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi
Vol 13, Article 10 (pp 1-19)
On the Hardness of Approximating Balanced Homogenous 3-Lin
by Johan Håstad and Rajsekar Manokaran
Vol 11, Article 18 (pp 445-469) [Boolean Spec Issue]
On some extensions of the FKN theorem
by Jacek Jendrej, Krzysztof Oleszkiewicz, and Jakub O. Wojtaszczyk
Vol 11, Article 10 (pp 257-283) [APRX-RND13 Spec Issue]
On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems
by Per Austrin, Rajsekar Manokaran, and Cenny Wenner
Vol 11, Article 7 (pp 221-235) [APRX-RND12 Spec Issue]
The Projection Games Conjecture and the NP-Hardness of ln $n$-Approximating Set-Cover
by Dana Moshkovitz
Vol 9, Article 28 (pp 863-887) [Boolean Spec Issue]
A Two-Prover One-Round Game with Strong Soundness
by Subhash Khot and Muli Safra
Vol 9, Article 11 (pp 413-435)
Improved Inapproximability Results for Maximum $k$-Colorable Subgraph
by Venkatesan Guruswami and Ali Kemal Sinop
Vol 7, Article 3 (pp 27-43)
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs
by Per Austrin, Subhash Khot, and Muli Safra
Vol 5, Article 8 (pp 141-172)
Parallel Repetition: Simplification and the No-Signaling Case
by Thomas Holenstein
Vol 5, Article 4 (pp 83-117)
SDP Gaps and UGC-hardness for Max-Cut-Gain
by Subhash Khot and Ryan O'Donnell
Vol 5, Article 1 (pp 1-42)
The Power of Unentanglement
by Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor
Vol 3, Article 6 (pp 103-128)
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number
by David Zuckerman
Vol 2, Article 9 (pp 173-183)
Tolerant Versus Intolerant Testing for Boolean Properties
by Eldar Fischer and Lance Fortnow
Vol 1, Article 7 (pp 119-148)
Query Efficient PCPs with Perfect Completeness
by Johan Håstad and Subhash Khot