UG-hardness to NP-hardness by losing half

DOI10.4086/TOC.2022.V018A005MaRDI QIDQ5077147OpenAlexFDO

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

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)

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

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)