  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-satisfiable. It is known that the CSPs that admit
efficient robust satisfaction algorithms are precisely those of bounded width,
i.e., CSPs whose satisfiability can be checked by a simple local consistency
algorithm (eg., 2-SAT or Horn-SAT in the Boolean case). While the exact
satisfiability of a bounded width CSP can be checked by combinatorial
algorithms, the robust algorithm is based on rounding a canonical Semidefinite
programming(SDP) relaxation.
  In this work, we initiate the study of robust satisfaction algorithms for
promise CSPs, which are a vast generalization of CSPs that have received much
attention recently. The motivation is to extend the theory beyond CSPs, as well
as to better understand the power of SDPs. We present robust SDP rounding
algorithms under some general conditions, namely the existence of particular
high-dimensional Boolean symmetries known as majority or alternating threshold
polymorphisms. On the hardness front, we prove that the lack of such
polymorphisms makes the PCSP hard for all pairs of symmetric Boolean
predicates. Our method involves a novel method to argue SDP gaps via the
absence of certain colorings of the sphere, with connections to sphere Ramsey
theory.
  We conjecture that PCSPs with robust satisfaction algorithms are precisely
those for which the feasibility of the canonical SDP implies (exact)
satisfiability. We also give a precise algebraic condition, known as a minion
characterization, of which PCSPs have the latter property.
