A new point of NP-hardness for unique games

DOI10.1145/2213977.2214005zbMath1286.68206OpenAlexW2073029179WikidataQ29028747 ScholiaQ29028747MaRDI QIDQ5415482

No author found.

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2213977.2214005

zbMATH Keywords

NP-hardnesshardness of approximationunique games conjecture

Mathematics Subject Classification ID

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

Related Items (4)

New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover ⋮ Unnamed Item ⋮ Inapproximability of unique games in fixed-point logic with counting ⋮ On non-optimally expanding sets in Grassmann graphs

This page was built for publication: A new point of NP-hardness for unique games