{'fraction_non_alphanumeric': 0.04829354404841964, 'fraction_numerical': 0.009835238735709483, 'mean_word_length': 4.110180412371134, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs

In 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 benefited from multiple breakthroughs [BKO19, WZ19] due to a systematic study of promise CSPs under the lens of"polymorphisms,"operations that map tuples in the strict form of each constraint to a tuple in its 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 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 theorem and shed further light on how symmetries of polymorphisms enable algorithms.


Introduction
A central challenge in the theory of algorithms is to understand the mathematical structure (or lack thereof) that governs the efficient tractability (or intractability) of a computational problem. For the class of constraint satisfaction problems (CSP), a rich algebraic theory culminating in the recent resolution of the Feder-Vardi dichotomy conjecture [FV98] in [Bul17,Zhu17] has established a striking link between problem structure and its tractability. In particular, a CSP is efficiently solvable if and only if its defining relations admit an "interesting" polymorphism. Informally, a polymorphism is a function whose component-wise action preserves membership in the relations defining the CSP, and "interesting" means that the function obeys some non-trivial symmetry. As an example, for the (efficiently solvable) CSP corresponding to linear equations over a ring R, the 3-ary function f (x, y, z) = x − y + z is a polymorphism (capturing the fact that if v 1 , v 2 , v 3 are solutions to a linear system, then so is v 1 − v 2 + v 3 ), and it obeys the socalled Mal'stev symmetry f (x, y, y) = f (y, y, x) for all x, y ∈ R. Indeed, generalizing Gaussian elimination, any CSP with such a Mal'stev polymorphism is efficiently tractable [Bul02,BD06].
Recently, an exciting new direction of study has emerged in the rich backdrop of the complexity dichotomy for CSPs. This concerns a vast generalization of the CSP framework to the class of promise constraint satisfaction problems (PCSP). In a promise CSP, each constraint comes in two forms: "strict" and "weak." Given an instance of a PCSP, one must distinguish between being able to satisfy all the strict constraints versus not being able to satisfy all the weak constraints. (This is the decision version; in the search version, given an instance with a promised assignment satisfying the strong form of the constraints, one seeks an assignment satisfying the weak form of the constraints.) A prime example of a PCSP is the approximate graph coloring problem, where one seeks a color a graph using more colors than its chromatic number.
The formal study of promise CSPs originated in [AGH17] who classified the complexity of a PCSP called (2 + ǫ)-SAT. They further defined an extension of polymorphisms to the promise setting and postulated that the structure of those polymorphisms might govern the complexity of a PCSP. (This extension of polymorphisms to the promise setting is quite natural, requiring that the operation map tuples obeying the strict form a constraint to a tuple satisfying its weak form.) Building on the impetus of [AGH17], the authors of the present paper systematically studied PCSPs under the polymorphic lens and established promising links to the universal-algebraic framework developed for CSPs [BG18,BG19]. It emerged from these works that a rich enough family of polymorphisms leads to efficient algorithms, whereas severely limited polymorphisms are a prescription for hardness. However, unlike for CSPs, there is no sharp transition between these cases -the significant difficulty being that, unlike for CSPs, polymorphisms for PCSPs are not closed under composition and lack the rich algebraic structure of a clone (c.f., [BKW17]). This nascent algebraic theory for PCSPs was lifted to a more abstract level in [BKO19,BBKO19] and also led to concrete breakthroughs in approximate graph coloring/homomorphisms [BKO19, KO19,WŽ19]. In particular, while our previous works [BG18,BG19] focused on the actual form of the polymorphisms, the results of [BKO19] reveal that it is not the polymorphisms themselves, but rather solely the symmetries they possess, that capture the complexity of the associated PCSP, extending a similar phenomenon known earlier for CSPs [BOP18].
This work concerns the theme of designing algorithms for PCSP based on a rich enough family of polymorphisms. Our main result is that the decision version of an arbitrary PCSP admitting an infinite family of symmetric polymorphisms -i.e., polymorphisms which are invariant under any permutation of inputs -is tractable (see Theorem 3.1). Our result also extends to the case of block-symmetric polymorphisms (see Theorem 4.1). That is, the coordinates can be partitioned into "blocks" such that the function is invariant under permutations within each block. Notably, in the block-symmetric case the algorithm is identical-only the analysis changes. Furthermore, the number of blocks is irrelevant, the only assumption we need is that the minimum block size can be made arbitrarily large.
Further our algorithm is very simple -it checks if the canonical linear programming (LP) relaxation of the PCSP is feasible, and if so, if additionally (a slight adaptation of) a canonical affine relaxation is feasible. The algorithm outputs satisfiable if both these relaxations are feasible. The polymorphisms are not used in the algorithm itself and only enter the analysis. The analysis is short but subtle -if we had symmetric polymorphisms of all arities then it is known that basic LP relaxation itself correctly decides satisfiability, as one can round the fractional solution to a satisfying assignment using the polymorphism after clearing denominators of the fractional solution [KOT + 12, BKW17]. If polymorphisms only exist of certain arities (e.g., all odd majorities), then the LP alone doesn't suffice. We solve a linear system over the integers corresponding to the affine relaxation which lets us adjust the LP solution to match the arity at which a polymorphism exists. As a subtle twist, the affine relaxation is not of the original PCSP, but rather a refinement of the CSP which results from throwing out assignments to constraints which were ruled out by the basic LP.
It should be pointed out that we only solve the decision version of the PCSP, and not the search version. Unlike CSPs, for promise CSP there is no known reduction from search to decision, even for special cases like approximate graph coloring. Our work might be indicative of the subtle relationship between the search and decision problems for promise CSPs.
We now compare our result here with our previous work [BG19] where we gave an algorithm to solve (the search version of) any PCSP that admits an infinite family of structured symmetric polymorphisms. Examples of such structured families include threshold and threshold-periodic polymorphisms. The value a threshold polymorphism (for a Boolean PCSP) takes depends on which of a finite number of intervals the fraction of 1s in the input belongs. (A basic example consists of Majority functions of odd arities, which are polymorphisms for 2-SAT.) A threshold-periodic polymorphism can have a periodic behavior depending on which interval the Hamming weight belongs to -for example it can be Majority for relative weights in (1/3, 2/3) and parity outside this interval. More generally, one can generalize to the non-Boolean case, as well as for the block-symmetric case, via regional polymorphisms whose value depends on the geometric region in which the vector of frequencies of the inputs to the polymorphisms lies. Due to this geometric interpretation, [BG19] assumes a fixed number of blocks (corresponding to a fixed dimension), whereas our new algorithm and analysis is independent of the number of blocks. The algorithm was a combination of solving the LP relaxation (albeit over a special ring like Z[ √ 2] rather than the rationals) and the affine relaxation over a large enough finite ring. The analysis relied on the special structure of the polymorphisms (beyond their full symmetry). In contrast, our result here is more general, and only requires the polymorphism to be a symmetric function -its exact specifics or structure do not matter. It is encouraging that our methodology is consistent with the algebraic result in [BKO19] that the symmetries possessed by the polymorphisms capture the complexity of the PCSP.
Our result and methods have significance even for normal (non-promise) CSPs. For instance, we get a single unified algorithm to solve all non-trivial tractable cases of Boolean CSPs in Schaefer's classic dichotomy theorem [Sch78], namely 2-SAT, Horn-SAT (or its dual), and Mod-2 Linear Equations. The two main techniques to solve CSPs are local propagation based algorithms (which work for the so-called bounded-width CSPs [BK14, KOT + 12], etc.) and Gaussian elimination (which is a global algorithm that works for linear equations). The major difficulty in proving the full CSP dichotomy was tackling the complicated ways in which these two very different algorithms might need to be interlaced to solve a general CSP. It is our hope that this work serves as an impetus toward the potential discovery of a more modular CSP algorithm that incorporates together linear programming or its extensions (like Sherali-Adams, or semidefinite programming) and linear equation solving. In this light, it is encouraging that full symmetry of the polymorphisms, which is indeed a strong assumption, is not the limit of our techniques, which also extend to the block-symmetric case.
To put this work in further context, except for [BG19] as mentioned previously, nearly all works in the PCSP literature [AGH17, BG18, FKOS19] focus primarily on the structure of the relations. In particular, [BG18,FKOS19] characterized the complexity of all Boolean symmetric relations (rather than symmetric polymorphisms) which encompass many of the known tractable cases of Boolean PCSP. As classified by [FKOS19], all the relevant tractable polymorphisms are either symmetric functions or one special case of block-symmetric known as alternative threshold (and variants). Thus, in the context of PCSPs, the single algorithm in this paper supersedes this program in addition to [BG19]. See Section 4 for further discussion.

Notation
We let any finite set D denote a domain. A relation is a subset R ⊆ D k for any positive integer k. A template, often denoted by Two templates for which there exists a homomorphism from the first to the second is called a promise template and is denoted as (A, B).

PCSP: Decision and Search
A CSP over a template A is a CNF formula over the relations of A. Likewise, a promise CSP (or PCSP) over a promise template (A, B) is a pair of CSPs with identical structure with each R i in the first CSP replaced with the corresponding S i in the second CSP. Explicitly, we let x 1 , . . . , x n denote the variables. We let A 1 , . . . , A m ∈ A denote the constraints for the first CSP and B 1 , . . . , B m ∈ B denote the constraints for the second CSP. In particular, if A j = R i for some i ∈ I then B j = S i for that same i. We let ar(A j ) denote the number of arguments A j takes (which is the same for B j ). The explicit CSPs are then. Ψ A (x 1 , . . . , x n ) := A 1 (x i 1,1 , . . . , x i 1,ar(A 1 ) ) ∧ A 2 (x i 2,1 , . . . , x i 2,ar(A 2 ) ) · · · ∧ A m (x i m,1 , . . . , x i m,ar(Am) ) Ψ B (x 1 , . . . , x n ) := B 1 (x i 1,1 , . . . , x i 1,ar(B 1 ) ) ∧ B 2 (x i 2,1 , . . . , x i 2,ar(B 2 ) ) · · · ∧ B m (x i m,1 , . . . , x i m,ar(Bm) ) Note that because of the homomorphism σ from A to B, satisfiability of the first CSP implies satisfiability of the second CSP. We let PCSP-Decision(Γ) denote the decision problem of distinguishing between satisfiability of the first CSP from lack of satisfiability of the second CSP. We let PCSP-Search(Γ) denote the search problem of finding a satisfying assignment to the second CSP under the promise that the first is satisfiable.

Polymorphisms
In other words, consider any D L×ar R i matrix M , where each row is a satisfying assignment to R i . Let X ∈ E ar R i be the result of applying f to each column of M . Then, X ∈ S i . We say that L is the arity of f . We let Pol(A, B) denote the set of polymorphisms of (A, B) (of all arities).

Basic LP and Affine Relaxation
As is well-studied in the CSP literature (e.g., [RS09,TŽ17]), we consider the canonical linear programming relaxation of a CSP, often refer to as the "Basic LP." For our CSP instance Ψ A , we represent the assignment to x i by a (rational) probability distribution of weights {w i (d)} d∈D summing to 1. We also have a probability distribution over the satisfying assignments to each constraint, which we denote as p j (y), where j ∈ [m] is the index of the constraint and y ∈ A j is the potential assignment. Explicitly, the linear constraints are as follows.
We let LP Q (Ψ A ) denote the rational polytope of solutions. By a theorem of [GLS93] (c.f., [BG19]), we can efficiently find an relative interior point in this polytope. In particular, at such a point, each coordinate is nonnegative if and only if it is non-negative at some point in the polytope. 1 In addition to the Basic LP, we also consider the affine relaxation of a Promise CSP. In essence we solve the same linear system, but instead of enforcing each variable to be a nonnegative rational, we enforce that it is an integer (possibly negative). This can be solved in polynomial time via [KB79] (see also [BG19] for a more detailed discussion of this approach). We let (r i (1), . . . , r i (d)) ∈ Z d replace (w i (1), . . . , w i (d)) and q i (y) ∈ Z replace p i (y) ∈ Q. Explicitly, We let Aff Z (Ψ A ) denote the integral lattice of solutions 3 Algorithm for Symmetric Polymorphisms In our algorithm, we seek to throw out any assignment to a constraint with weight 0 . In particular, for each constraint A i , we let A ′ i ⊆ A i be the set of assignments which have nonzero weight. We let Ψ ′ A be the refined CSP built from A ′ i 's instead of A i 's. The algorithm is presented in Figure 1.
1. Find a relative interior point in LP Q (Ψ A ). If no solution exists, Reject.

Refine Ψ A to Ψ ′
A by throwing out assignments to constraints which have weight 0.
3. If Aff Z (Ψ ′ A ) is empty, Reject. Else, Accept. As stated in the introduction, both the algorithm and the proof are structured similar to those of [KOT + 12] and [BG19]. Like in those works, the weights of the LP solution and affine relaxation are used to construct a list of assignments which are plugged into the relevant polymorphism. The novel contribution here is that a single argument can cover any infinite symmetric family of polymorphisms.
Proof. If the Basic LP fails to have a solution, then Ψ A is not satisfiable. Note that the refinement Ψ ′ A includes every possible assignment which is in the support of some LP solution, including integral solutions. Thus, any solution to Ψ A is also a solution to Ψ ′ A . Thus, if the affine relaxation of Ψ ′ A fails to have a solution then Ψ ′ A (and thus Ψ A ) is unsatisfiable. We use the notation of Section 2.3. Among all the coordinates in the LP solution-the w's and P 's-let ℓ be the least common denominator of these rational numbers. Let M be the maximum absolute value of any integer which appears in the affine solution (both the variable weights and the constraint weights). Let f : D L → E be a symmetric polymorphism of arity L > (M + 1)ℓ 2 . Now write L = uℓ + v where u ∈ Z + and v ∈ {0, . . . , ℓ − 1}. Note that u ≥ (M + 1)ℓ.
We seek to show there exists an assignment to Ψ B . For each i ∈ [n] and d ∈ D, let For a fixed i ∈ [n], note that by Eq. (3) and (6) Also, for fixed i ∈ [n] and d ∈ D, either w i (d) = 0, which implies that r i (d) = 0 by the refinement, so W i (d) = 0. Otherwise, w i (d) ≥ 1/ℓ, so We claim that the assignment satisfies Ψ B . To verify this, fix a constraint B j (with A ′ j the corresponding constraint in Ψ ′ A ), for j ∈ [m] and assume WLOG it is on variables x 1 , . . . , x k .
By Eqs. 4 and 7, Since p j (y) > 0 for all y ∈ A ′ j by definition, we have by similar logic as for W i (d) that Further note that by Eqs. 5 and 8 For each j ∈ [m] consider a matrix M (j) ∈ D L×k , where exactly P j (y) of the rows are equal to y. When f is applied to the columns of M (j), the result will satisfy B i (x 1 , . . . , x k ) in Ψ B . For all i ∈ [k] and d ∈ D, the number of times that d ∈ D appears in column i is precisely W i (d) by Eq. (9). Thus, f applied to the columns is precisely (X 1 , . . . , X k ). In other words, the assignment of X i for i ∈ [n] satisfies Ψ B , so the algorithm is correct.
Remark. Another algorithm which works is to solve the Basic LP of Ψ A , but to find the solution in Z[ √ 2] instead of Q, using our algorithm from [BG19]. In this case, Steps 2 and 3 can be omitted. This works because the algorithm for finding such a solution needs to solve the rational linear program and solve the subsequent linear system. Further details are omitted.

Extension to Block Symmetric Polymorphisms
We say that an operator f : D L → E. is block-symmetric if there exists a partition of the coordinates of f into blocks B 1 ∪ · · · ∪ B k = [L] such that f is permutation-invariant within each coordinate block B i . We define the width of f to be the minimum size of any block.Note that a function f might have different partitions into symmetric blocks, we define the width to be the maximum width over all such partitions. A natural example of a block symmetric polymorphism is alternating threshold first studied in [BG18] AT (x 1 , . . . , In this case, the blocks are the odd and even coordinates. This polymorphism arises in the context of A corresponding to 1-in-3 SAT and B corresponding to NAE-SAT. Recent work shows that this PCSP, although simple to state, is not reducible from any finite-domain CSP [BBKO19].
We now show an analogue of Theorem 3.1 for block-symmetric polymorphisms. Remarkably, the algorithm is identical to the one for ordinary symmetric polymorphisms and is independent of the number of blocks. In particular, it could be that the Promise CSP has finitely many polymorphisms for any particular number of blocks, yet has infinitely many block-symmetric polymorphisms of increasing width.
As discussed in [BG19,FKOS19], nearly all known tractable Boolean CSPs are have polymorphisms which are either symmetric (such as threshold functions) or block-symmetric (such as alternating threshold). Thus, except for those PCSPs which are a "homomorphic relaxations" of a larger finite domain (P)CSP (c.f., [BG19,BBKO19]), the algorithm presented here supersedes those works in the context of decision PCSP. Proof. The proof proceeds much like that of Theorem 3.1. As before, we know that if the algorithm rejects, when Ψ A is unsatisfiable. We seek to show that if the algorithm accepts, then Ψ B is satisfiable.
Again, let ℓ be the least common denominator of all coordinates in the LP solution. Let M be the maximum absolute value of any integer which appears in the affine solution. Let f : D B 1 ∪···∪Bκ → E be a block-symmetric polymorphism such that each block B b , with b ∈ [κ], has size greater than (M + 1)ℓ 2 . Let L b = |B b |. Similar to before, for all b ∈ [κ], write We seek to show there exists an assignment to Ψ B . For each b ∈ [κ], i ∈ [n] and d ∈ D, let For a fixed b ∈ [κ] and i ∈ [n], by similar logic to the proof of Theorem 3.1, we have that We now claim that the assignment For all b ∈ [κ] and assignments y ∈ A ′ j define P b,j (y) := u b ℓp j (y) + v b q j (y).
By Eqs. 4 and 7, By similar logic in previous arguments, Further note that by Eqs. 5 and 8 For each j ∈ [m] consider a matrix M (j) ∈ D L×k , where exactly P b,j (y) of the rows are equal to y in the rows indexed by block B b . When f is applied to the columns of M (j), the result will satisfy B i (x 1 , . . . , x k ) in Ψ B . For all i ∈ [k] and d ∈ D, the number of times that d ∈ D appears in column i and row-block B b is precisely W b,i (d) by Eq. (10). Thus, f applied to the columns is precisely (X 1 , . . . , X k ). In other words, the assignment of X i for i ∈ [n] satisfies Ψ B , so the algorithm is correct.

Concluding thoughts
We conclude with a few natural directions of future inquiry raised by this work.

Decision vs. Search
Inspecting the proofs of Theorems 3.1 and 4.1, in order to yield a search algorithm, it suffices to compute: , . . .).
In our previous work [BG19], we circumvented this problem by assuming that f has special structure (such as being a threshold function, etc.). Even then, we often only assumed that you had oracle access to the structure of f . Thus, except for some simple cases studied in the paper, truly polynomial-time search algorithms remain elusive. Perhaps one could hope for a search algorithm like the decision algorithm presented in this paper which is oblivious to the underlying polymorphisms (as long as they are symmetric/block-symmetric).
Question 5.1. Is there an "oblivious" polynomial-time algorithm for the search version of Promise CSPs with infinitely many symmetric polymorphisms?
Otherwise, one could hope to prove a "structure theorem" that every Promise CSP with infinitely many symmetric polymorphisms also has an infinite threshold-periodic family. As [BG19] shows, such polymorphisms can get exceedingly complicated, suggesting that such a characterization may only be possible in the Boolean case.
Question 5.2. Does every Boolean PCSP with infinitely many symmetric polymorphisms have an infinite threshold-periodic family?
Even without a structure theorem, one could perhaps hope to compute the pertinent values of f "on the fly," but this seems difficult in our current formulation as the arity of f could be exponentially large in the input size!

Characterization of identities
As mentioned in the introduction, the symmetries possessed by the associated polymorphisms dictate the complexity of a PCSP. Formally, these symmetries are captured via identities which consist of systems of equations which the polymorphisms satisfy. For instance, [BK12] showed that every tractable CSP has infinitely many polymorphisms which satisfies the cyclic identity -that is f (x 1 , x 2 , . . . , x L ) = f (x 2 , x 3 , . . . , x L , x 1 ) (universally over all x i 's in the domain).
In the context of decision PCSPs, we do not know the limits of the algorithm presented in Figure 1.
Question 5.3. What is the most general set of identities for which the algorithm presented in Figure 1 succeeds?
For example, could it give a polynomial-time algorithm for a more general set of identities than block symmetry? The authors are highly doubtful it could extend to cyclic polymorphisms, but if it were to, it would imply a surprisingly simple algorithm which works for all tractable CSPs simultaneously.