Articles under category:
Probabilistically Checkable Proofs
Probabilistically Checkable Proofs
|
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 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 10, Article 14 (pp 359-388)
Approximation Resistance on Satisfiable Instances for Sparse Predicates by Sangxia Huang |
|
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 27 (pp 845-862)
[Boolean Spec Issue]
Satisfying Degree-$d$ Equations over $GF[2]^n$ by Johan Håstad |
|
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 |