ECCC-Report TR20-004https://eccc.weizmann.ac.il/report/2020/004Comments and Revisions published for TR20-004en-usThu, 24 Sep 2020 23:38:26 +0300
Revision 1
| The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs |
Joshua Brakensiek,
Venkatesan Guruswami,
Marcin Wrochna,
Stanislav Zivny
https://eccc.weizmann.ac.il/report/2020/004#revision1In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: “strict” and “weak,” and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not being able to satisfy all the weak constraints. The most commonly cited example of a promise CSP is the approximate graph coloring problem--which has recently seen exciting progress [BKO19, WZ20] benefiting from a systematic algebraic approach to promise CSPs based on “polymorphisms,” operations that map tuples in the strict form of each constraint to tuples in the corresponding weak form.
In this work, we present a simple algorithm which in polynomial time solves the decision problem for all promise CSPs that admit infinitely many symmetric polymorphisms, which are invariant under arbitrary coordinate permutations. This generalizes previous work of the first two authors [BG19]. We also extend this algorithm to a more general class of block-symmetric polymorphisms. As a corollary, this single algorithm solves all polynomial-time tractable Boolean CSPs simultaneously. These results give a new perspective on Schaefer’s classic dichotomy theorem and shed further light on how symmetries of polymorphisms enable algorithms. Finally, we show that block symmetric polymorphisms are not only sufficient but also necessary for this algorithm to work, thus establishing its precise power.
Thu, 24 Sep 2020 23:38:26 +0300https://eccc.weizmann.ac.il/report/2020/004#revision1
Paper TR20-004
| The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs |
Joshua Brakensiek,
Venkatesan Guruswami,
Marcin Wrochna,
Stanislav Zivny
https://eccc.weizmann.ac.il/report/2020/004In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not being able to satisfy all the weak constraints. The most commonly cited example of a promise CSP is the approximate graph coloring problem--which has recently seen exciting progress [BKO19, WZ20] benefiting from a systematic algebraic approach to promise CSPs based on "polymorphisms," operations that map tuples in the strict form of each constraint to tuples in the corresponding weak form.
In this work, we present a simple algorithm which in polynomial time solves the decision problem for all promise CSPs that admit infinitely many symmetric polymorphisms, that is the coordinates are permutation invariant. This generalizes previous work of the first two authors [BG19]. We also extend this algorithm to a more general class of block-symmetric polymorphisms. As a corollary, this single algorithm solves all polynomial-time tractable Boolean CSPs simultaneously. These results give a new perspective on Schaefer's classic dichotomy theorem and shed further light on how symmetries of polymorphisms enable algorithms. Finally, we show that block symmetric polymorphisms are not only sufficient but also necessary for this algorithm to work, thus establishing its precise power.
Fri, 17 Jan 2020 04:50:12 +0200https://eccc.weizmann.ac.il/report/2020/004