Articles under category:
Vol 13, Article 3 (pp 1-24) [APRX-RND15 Spec Issue]
Towards a Characterization of Approximation Resistance for Symmetric CSPs
by Venkatesan Guruswami and Euiwoong Lee
Vol 12, Article 15 (pp 1-29) [APRX-RND14 Spec Issue]
Lowest-Degree $k$-Spanner: Approximation and Hardness
by Eden Chlamtáč and Michael Dinitz
Vol 12, Article 6 (pp 1-11) [NOTE]
Simple Proof of Hardness of Feedback Vertex Set
by Venkatesan Guruswami and Euiwoong Lee
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 11, Article 6 (pp 183-219)
How Hard Is It to Approximate the Jones Polynomial?
by Greg Kuperberg
Vol 10, Article 14 (pp 359-388)
Approximation Resistance on Satisfiable Instances for Sparse Predicates
by Sangxia Huang
Vol 10, Article 9 (pp 217-236)
Improved Inapproximability for TSP
by Michael Lampis
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 24 (pp 759-781) [APRX-RND12 Spec Issue]
Hardness of Vertex Deletion and Project Scheduling
by Ola Svensson
Vol 9, Article 23 (pp 703-757) [APRX-RND12 Spec Issue]
Circumventing $d$-to-$1$ for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four
by Cenny Wenner
Vol 9, Article 22 (pp 685-702)
Hamming Approximation of NP Witnesses
by Daniel Sheldon and Neal E. Young
Vol 9, Article 11 (pp 413-435)
Improved Inapproximability Results for Maximum $k$-Colorable Subgraph
by Venkatesan Guruswami and Ali Kemal Sinop
Vol 9, Article 3 (pp 117-142)
Inapproximability of NP-Complete Variants of Nash Equilibrium
by Per Austrin, Mark Braverman, and Eden Chlamtáč
Vol 8, Article 23 (pp 513-531)
Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
by Ishay Haviv and Oded Regev
Vol 8, Article 22 (pp 487-512)
Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction
by Daniele Micciancio
Vol 8, Article 11 (pp 239-267)
Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set
by Venkatesan Guruswami and Yuan Zhou
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 4 (pp 83-117)
SDP Gaps and UGC-hardness for Max-Cut-Gain
by Subhash Khot and Ryan O'Donnell
Vol 3, Article 6 (pp 103-128)
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number
by David Zuckerman
Vol 3, Article 3 (pp 45-60)
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
by Ishay Haviv, Oded Regev, and Amnon Ta-Shma
Vol 1, Article 7 (pp 119-148)
Query Efficient PCPs with Perfect Completeness
by Johan Håstad and Subhash Khot