On Robust Promise CSPs: A Boolean Dichotomy, Sharp Quantitative Bounds, and Soft-Equality TransferResearch Paper
A promise constraint satisfaction problem (PCSP) asks, given an instance that is satisfiable with respect to a strong family of relations, for an assignment satisfying a weaker family. Its robust version asks for more: when some assignment violates only an fraction of the strong constraints, an algorithm must return an assignment that violates at…