Robust algorithms with polynomial loss for near-unanimity CSPs

Víctor Dalmau, Marcin Kozik, Andrei Krokhin +3

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…