TY - GEN

T1 - A characterization of approximation resistance for even k-partite CSPs

AU - Austrin, Per

AU - Khot, Subhash

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - approximation resistance

KW - unique games conjecture

UR - http://www.scopus.com/inward/record.url?scp=84873348647&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84873348647&partnerID=8YFLogxK

U2 - 10.1145/2422436.2422459

DO - 10.1145/2422436.2422459

M3 - Conference contribution

AN - SCOPUS:84873348647

SN - 9781450318594

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

SP - 187

EP - 196

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

T2 - 2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013

Y2 - 9 January 2013 through 12 January 2013

ER -