Articles under category:
Inapproximability
Inapproximability
|
Volume 9, Article 3 (pages 117-142)
Inapproximability of NP-Complete Variants of Nash Equilibrium by Per Austrin, Mark Braverman, and Eden Chlamtáč |
|
Volume 8, Article 23 (pages 513-531)
Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors by Ishay Haviv and Oded Regev |
|
Volume 8, Article 22 (pages 487-512)
Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction by Daniele Micciancio |
|
Volume 8, Article 11 (pages 239-267)
Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set by Venkatesan Guruswami and Yuan Zhou |
|
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 4 (pages 83-117)
SDP Gaps and UGC-hardness for Max-Cut-Gain by Subhash Khot and Ryan O'Donnell |
|
Volume 3, Article 6 (pages 103-128)
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number by David Zuckerman |
|
Volume 3, Article 3 (pages 45-60)
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy by Ishay Haviv, Oded Regev, and Amnon Ta-Shma |
|
Volume 1, Article 7 (pages 119-148)
Query Efficient PCPs with Perfect Completeness by Johan Håstad and Subhash Khot |