UG-hardness to NP-hardness by losing half

DOI10.4086/TOC.2022.V018A005OpenAlexW4226342274MaRDI QIDQ5077147FDOQ5077147

Authors: Amey Bhangale, Subhash Khot 

Publication date: 18 May 2022

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2022.v018a005

Recommendations

• UG-hardness to NP-hardness by losing half
• A new point of NP-hardness for unique games
• Towards a proof of the 2-to-1 games conjecture?
• scientific article; zbMATH DE number 6823767
• Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)

zbMATH Keywords

inapproximabilityNP-hardnessunique games conjecture

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Theory of computing (68Qxx)

Cited In (1)

• UG-hardness to NP-hardness by losing half

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 Q5077147)