### 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 language | English (US) |
---|---|

Title of host publication | ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science |

Pages | 187-196 |

Number of pages | 10 |

DOIs | |

State | Published - 2013 |

Event | 2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013 - Berkeley, CA, United States Duration: Jan 9 2013 → Jan 12 2013 |

### Publication series

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

### Other

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

Country | United States |

City | Berkeley, CA |

Period | 1/9/13 → 1/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