A characterization of approximation resistance for even k-partite CSPs

DOI10.1145/2422436.2422459zbMath1361.68096arXiv1301.2731MaRDI QIDQ2986869

Subhash A. Khot, Per Austrin

Publication date: 16 May 2017

Published in: Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1301.2731

zbMATH Keywords

unique games conjecture; approximation resistance

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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