Robust Approximation and the Arity Barrier at Width Two

Nathan Benedetto Proença, Koppány István Encz, Monaldo Mastrolilli

Zwick's algorithm for Horn satisfiability shows that constraints of unbounded arity can admit a robust approximation guarantee independent of the arity. For finite constraint langu…