English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

For a constraint satisfaction problem (CSP), a robust satisfaction algorithmis one that outputs an assignment satisfying most of the constraints oninstances that are near-satisfiable. It is known that the CSPs that admitefficient robust satisfaction algorithms are precisely those of bounded width,i.e., CSPs whose satisfiability can be checked by a simple local consistencyalgorithm (eg., 2-SAT or Horn-SAT in the Boolean case). While the exactsatisfiability of a bounded width CSP can be checked by combinatorialalgorithms, the robust algorithm is based on rounding a canonical Semidefiniteprogramming(SDP) relaxation.  In this work, we initiate the study of robust satisfaction algorithms forpromise CSPs, which are a vast generalization of CSPs that have received muchattention recently. The motivation is to extend the theory beyond CSPs, as wellas to better understand the power of SDPs. We present robust SDP roundingalgorithms under some general conditions, namely the existence of particularhigh-dimensional Boolean symmetries known as majority or alternating thresholdpolymorphisms. On the hardness front, we prove that the lack of suchpolymorphisms makes the PCSP hard for all pairs of symmetric Booleanpredicates. Our method involves a novel method to argue SDP gaps via theabsence of certain colorings of the sphere, with connections to sphere Ramseytheory.  We conjecture that PCSPs with robust satisfaction algorithms are preciselythose for which the feasibility of the canonical SDP implies (exact)satisfiability. We also give a precise algebraic condition, known as a minioncharacterization, of which PCSPs have the latter property.

SDPs and Robust Satisfiability of Promise CSP