### Abstract

An instance of the constraint satisfaction problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints. An approximation algorithm for a CSP is called robust if it outputs an assignment satisfying an (1 - g(ϵ))-fraction of constraints on any (1 ϵ)- satisfiable instance, where the loss function g is such that g(ϵ) → 0 as ϵ → 0. We study how the robust approximability of CSPs depends on the set of constraint relations allowed in instances, the so-called constraint language. All constraint languages admitting a robust polynomial-time algorithm (with some g) have been characterized by Barto and Kozik, with the general bound on the loss g being doubly exponential, specifically g(ϵ) = O((log log(1/ϵ))/ log(1/ϵ)). It is natural to ask when a better loss can be achieved, in particular polynomial loss g(ϵ) = O(ϵ^{1/k}) for some constant k. In this paper, we consider CSPs with a constraint language having a near-unanimity polymorphism. This general condition almost matches a known necessary condition for having a robust algorithm with polynomial loss. We give two randomized robust algorithms with polynomial loss for such CSPs: one works for any near-unanimity polymorphism and the parameter k in the loss depends on the size of the domain and the arity of the relations in Γ, while the other works for a special ternary near-unanimity operation called the dual discriminator with k = 2 for any domain size. In the latter case, the CSP is a common generalization of Unique Games with a fixed domain and 2-Sat. In the former case, we use the algebraic approach to the CSP. Both cases use the standard semidefinite programming relaxation for the CSP.

Original language | English (US) |
---|---|

Pages (from-to) | 1763-1795 |

Number of pages | 33 |

Journal | SIAM Journal on Computing |

Volume | 48 |

Issue number | 6 |

DOIs | |

State | Published - 2019 |

### Keywords

- Approximation algorithms
- Constraint satisfaction
- Near-unanimity polymorphism
- Robust algorithm

### ASJC Scopus subject areas

- Computer Science(all)
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Robust algorithms with polynomial loss for near-unanimity CSPs'. Together they form a unique fingerprint.

## Cite this

*SIAM Journal on Computing*,

*48*(6), 1763-1795. https://doi.org/10.1137/18M1163932