Articles under category:
Probabilistically Checkable Proofs
Probabilistically Checkable Proofs
|
Volume 7, Article 3 (pages 27-43)
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs by Per Austrin, Subhash Khot, and Muli Safra |
|
Volume 5, Article 8 (pages 141-172)
Parallel Repetition: Simplification and the No-Signaling Case by Thomas Holenstein |
|
Volume 5, Article 4 (pages 83-117)
SDP Gaps and UGC-hardness for Max-Cut-Gain by Subhash Khot and Ryan O'Donnell |
|
Volume 5, Article 1 (pages 1-42)
The Power of Unentanglement by Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor |
|
Volume 3, Article 6 (pages 103-128)
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number by David Zuckerman |
|
Volume 2, Article 9 (pages 173-183)
Tolerant Versus Intolerant Testing for Boolean Properties by Eldar Fischer and Lance Fortnow |
|
Volume 1, Article 7 (pages 119-148)
Query Efficient PCPs with Perfect Completeness by Johan Håstad and Subhash Khot |