UG-hardness to NP-hardness by losing half
From MaRDI portal
Publication:5091753
DOI10.4230/LIPIcs.CCC.2019.3OpenAlexW2964758001MaRDI QIDQ5091753
Subhash A. Khot, Amey Bhangale
Publication date: 27 July 2022
Full work available at URL: https://dblp.uni-trier.de/db/conf/coco/coco2019.html#BhangaleK19
Related Items (3)
Independent sets in semi-random hypergraphs ⋮ Pseudorandom sets in Grassmann graph have near-perfect expansion ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation resistant predicates from pairwise independence
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Proof verification and the hardness of approximation problems
- Approximation Resistance from Pairwise-Independent Subgroups
- Approximate Kernel Clustering
- On the power of unique 2-prover 1-round games
- Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
- Probabilistic checking of proofs
- Interactive proofs and the hardness of approximating cliques
- A Parallel Repetition Theorem
- On the Lovász Theta Function for Independent Sets in Sparse Graphs
- Bi-Covering: Covering Edges with Two Small Subsets of Vertices
- On independent sets, 2-to-2 games, and Grassmann graphs
- Towards a proof of the 2-to-1 games conjecture?
- On non-optimally expanding sets in Grassmann graphs
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
This page was built for publication: UG-hardness to NP-hardness by losing half
