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 -