UG-hardness to NP-hardness by losing half
From MaRDI portal
Publication:5091753
Recommendations
- UG-hardness to NP-hardness by losing half
- On uniform amplification of hardness in NP
- Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
- Nonuniform reductions and NP-completeness
- Nonuniform reductions and NP-completeness
- Hardness amplification within NP against deterministic algorithms
- Hardness amplification within NP
- The UGC hardness threshold of the l_p Grothendieck problem
- scientific article; zbMATH DE number 1775419
- The journey from NP to TFNP hardness
Cites work
- A Parallel Repetition Theorem
- Approximate kernel clustering
- Approximation Resistance from Pairwise-Independent Subgroups
- Approximation resistant predicates from pairwise independence
- Bi-covering: covering edges with two small subsets of vertices
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 1833409 (Why is no real title available?)
- Inapproximability of hypergraph vertex cover and applications to scheduling problems
- Inapproximability of vertex cover and independent set in bounded degree graphs
- Interactive proofs and the hardness of approximating cliques
- On independent sets, 2-to-2 games, and Grassmann graphs
- On non-optimally expanding sets in Grassmann graphs
- On the Lovász Theta Function for Independent Sets in Sparse Graphs
- On the NP-hardness of approximating ordering-constraint satisfaction problems
- On the power of unique 2-prover 1-round games
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
- Towards a proof of the 2-to-1 games conjecture?
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Cited in
(6)- UG-hardness to NP-hardness by losing half
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- scientific article; zbMATH DE number 7716602 (Why is no real title available?)
- Automated category tree construction: hardness bounds and algorithms
- Streaming approximation resistance of every ordering CSP
- Independent sets in semi-random hypergraphs
This page was built for publication: UG-hardness to NP-hardness by losing half
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091753)
