SDPs and Robust Satisfiability of Promise CSP

Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep

For a constraint satisfaction problem (CSP), a robust satisfaction algorithm is one that outputs an assignment satisfying most of the constraints on instances that are near-satisfi…