Articles under category:
Inapproximability
Inapproximability
|
Vol 18, Article 5 (pp 1-28)
[CCC19 Spec Issue]
UG-hardness to NP-hardness by Losing Half by Amey Bhangale and Subhash Khot |
|
Vol 17, Article 6 (pp 1-57)
Almost Polynomial Hardness of Node-Disjoint Paths in Grids by Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat |
|
Vol 16, Article 16 (pp 1-30)
A Characterization of Hard-to-Cover CSPs by Amey Bhangale, Prahladh Harsha, and Girish Varma |
|
Vol 16, Article 14 (pp 1-8)
[NOTE]
On the Hardness of Approximating the $k$-Way Hypergraph Cut problem by Chandra Chekuri and Shi Li |
|
Vol 16, Article 4 (pp 1-50)
[CCC18 Spec Issue]
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product by Lijie Chen |
|
Vol 13, Article 20 (pp 1-25)
The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems by F. Bruce Shepherd and Adrian R. Vetta |
|
Vol 13, Article 19 (pp 1-51)
[APRX-RND15 Spec Issue]
Improved NP-Inapproximability for $2$-Variable Linear Equations by Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright |
|
Vol 13, Article 15 (pp 1-24)
Tight Hardness of the Non-Commutative Grothendieck Problem by Jop Briët, Oded Regev, and Rishi Saket |
|
Vol 13, Article 10 (pp 1-19)
On the Hardness of Approximating Balanced Homogenous 3-Lin by Johan Håstad and Rajsekar Manokaran |
|
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 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 |