A characterization of approximation resistance for even k-partite CSPs

Per Austrin, Subhash Khot

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A constraint satisfaction problem (CSP) is said to be approximation resistant if it is hard to approximate better than the trivial algorithm which picks a uniformly random assignment. Assuming the Unique Games Conjecture, we give a characterization of approximation resistance for k-partite CSPs defined by an even predicate.

Original languageEnglish (US)
Title of host publicationITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science
Pages187-196
Number of pages10
DOIs
StatePublished - 2013
Event2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013 - Berkeley, CA, United States
Duration: Jan 9 2013Jan 12 2013

Publication series

NameITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science

Other

Other2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013
CountryUnited States
CityBerkeley, CA
Period1/9/131/12/13

Keywords

  • approximation resistance
  • unique games conjecture

ASJC Scopus subject areas

  • Management of Technology and Innovation
  • Computer Science (miscellaneous)

Fingerprint Dive into the research topics of 'A characterization of approximation resistance for even k-partite CSPs'. Together they form a unique fingerprint.

  • Cite this

    Austrin, P., & Khot, S. (2013). A characterization of approximation resistance for even k-partite CSPs. In ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science (pp. 187-196). (ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science). https://doi.org/10.1145/2422436.2422459