ECCC-Report TR18-059https://eccc.weizmann.ac.il/report/2018/059Comments and Revisions published for TR18-059en-usFri, 13 Jul 2018 17:52:12 +0300
Revision 1
| An Algorithmic Blend of LPs and Ring Equations for Promise CSPs |
Joshua Brakensiek,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2018/059#revision1Promise CSPs are a relaxation of constraint satisfaction problems where the goal is to find an assignment satisfying a relaxed version of the constraints. Several well known problems can be cast as promise CSPs including approximate graph and hypergraph coloring, discrepancy minimization, and interesting variants of satisfiability. Similar to CSPs, the tractability of promise CSPs can be tied to the structure of associated operations on the solution space called (weak) polymorphisms. However, compared to CSPs whose polymorphisms are well-structured algebraic objects called clones, polymorphisms in the promise world are much less constrained --- essentially any infinite family of functions obeying mild conditions can arise as polymorphisms. Under the thesis that non-trivial polymorphisms govern tractability, promise CSPs therefore provide a fertile ground for the discovery of novel algorithms.
In previous work, we classified all tractable cases of Boolean promise CSPs when the constraint predicates are symmetric. The algorithms were governed by three kinds of polymorphism families: (i) parity functions, (ii) majority functions, or (iii) a non-symmetric (albeit block-symmetric) family we called alternating threshold. In this work, we provide a vast generalization of these algorithmic results. Specifically, we show that promise CSPs that admit a family of ``regional-periodic" polymorphisms are solvable in polynomial time, assuming that determining which region a point is in can be computed in polynomial time. Such polymorphisms are quite general and are obtained by gluing together several functions that are periodic in the Hamming weights in different blocks of the input. For example, we can have functions that equal parity for relative Hamming weights up to 1/2, and Majority (so identically 1) for weights above 1/2.
Our algorithm is based on a novel combination of linear programming and solving linear systems over rings. We also abstract a framework based on reducing a promise CSP to a CSP over an infinite domain, solving it there (via the said combination of LPs and ring equations), and then rounding the solution to an assignment for the promise CSP instance. The rounding step is intimately tied to the family of polymorphisms, and clarifies the connection between polymorphisms and algorithms in this context. As a key ingredient, we introduce the technique of finding a solution to a linear program with integer coefficients that lies in a different ring (such as $\mathbb Z[\sqrt{2}]$) to bypass ad-hoc adjustments for lying on a rounding boundary.Fri, 13 Jul 2018 17:52:12 +0300https://eccc.weizmann.ac.il/report/2018/059#revision1
Paper TR18-059
| Combining LPs and Ring Equations via Structured Polymorphisms |
Joshua Brakensiek,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2018/059Promise CSPs are a relaxation of constraint satisfaction problems where the goal is to find an assignment satisfying a relaxed version of the constraints. Several well known problems can be cast as promise CSPs including approximate graph and hypergraph coloring, discrepancy minimization, and interesting variants of satisfiability. Similar to CSPs, the tractability of promise CSPs can be tied to the structure of associated operations on the solution space called (weak) polymorphisms. However, compared to CSPs whose polymorphisms are well-structured algebraic objects called clones, weak polymorphisms in the promise world are much less constrained --- essentially any infinite family of functions obeying mild conditions can arise as weak polymorphisms. Under the thesis that non-trivial polymorphisms govern tractability, promise CSPs therefore provide a fertile ground for the discovery of novel algorithms.
In previous work, we classified all tractable cases of Boolean promise CSPs when the constraint predicates are symmetric. The algorithms were governed by three kinds of polymorphism families: (i) parity functions, (ii) majority functions, or (iii) a non-symmetric (albeit block-symmetric) family we called alternating threshold. In this work, we provide a vast generalization of these algorithmic results. Specifically, we show that promise CSPs that admit a family of ``regional periodic" weak polymorphisms are solvable in polynomial time, assuming that determining which region a point is in can be computed in polynomial time. Such polymorphisms are quite general and are obtained by gluing together several functions that are periodic in the Hamming weights in different blocks of the input. For example, we can have functions that equal parity for relative Hamming weights up to 1/2, and Majority (so identically 1) for weights above 1/2.
Our algorithm is based on a novel combination of linear programming and solving linear systems over rings. We also abstract a framework based on embedding the promise CSP into a CSP over an infinite domain, solving it there (via the said combination of LPs and ring equations), and then rounding the solution to an assignment for the promise CSP instance. The rounding step is intimately tied to the family of weak polymorphisms, and clarifies the connection between polymorphisms and algorithms in this context. Along we way, we use a result due to Adler and Beling that linear programs over $\mathbb Z[\sqrt{2}]$ and similar algebraic extensions (instead of $\mathbb Q$) can be solved in weakly polynomial time.
Fri, 06 Apr 2018 05:35:55 +0300https://eccc.weizmann.ac.il/report/2018/059