CS Paper Radar

Maltsev Constraint Satisfaction Problems and Deterministic Logspace With Counting

Dejan Delic, Ali Syed

cs.CC ·submitted 2026-09-25 03:34 UTC · v1
theoryhot direction

Abstract

In this article, we prove that the problem of solving $\operatorname{CSP}(\mathbf{A})$, where $\mathbf{A}$ is a finite relational template which admits a Maltsev polymorphism is in a specific complexity class DET, which is related to the complexity of computing the determinant of a matrix with integer entries. Such a class is intimately related to well-studied MOD-logspace classes in the theory of computational complexity. To prove this fact, we develop a new algorithm for solving syntactically simple binary instances of Maltsev constraint satisfaction problems, rather different from the well-known Bulatov-Dalmau algorithm, which does not require the explicit use or knowledge of a Maltsev polymorphism of the template but, rather, utilizes a graph whose vertices are 2-generated subuniverses of $\mathbb{A}$, where $\mathbb{A}$ is the Maltsev algebra parametrizing $\operatorname{CSP}(\mathbf{A})$. The theoretical importance of this algorithm is reflected in two facts: (1) it places the problem $ \operatorname{CSP}(\mathbf{A})$ in a complexity class related to the deterministic logspace with counting, which, in itself, has a strong connection to a variety of standard algorithmic problems in linear algebra, and (2) it only makes use of the relational structure of the template without the need for the explicit use of a compatible Maltsev polymorphism, depending entirely on the strong ``symmetry" of constraints compatible with such polymorphisms and the knowledge of 2-generated subuniverses of $\mathbb{A}$.

Closest papers

Nearest neighbours by meaning across the whole index.

A Fast Algorithm for Maltsev Constraints

cs.CC cs.DS ·2026-10-06 ·Victor Lagerkvist
theory similarity 0.70
Abstract

The constraint satisfaction problem over a set of relations $Γ$ (CSP($Γ$)) is the computational problem of deciding if a set of constraints admits at least one solution. The classical complexity for finite-domain CSP($Γ$) is settled by the CSP dichotomy theorem: it is tractable if $Γ$ satisfies a non-trivial algebraic invariant and is NP-complete otherwise. However, not all these algebraic invariants result in efficient algorithms despite being theoretically tractable. A notable case that generalizes linear equations is that of Maltsev CSPs: an $n$-variable instance with $m$ constraints is solvable in roughly $O(n^8 \cdot m)$ time by Bulatov and Dalmau (SIAM J. Comput. 2006) or $O(n^4 \cdot m)$ time by Dyer and Richerby (SIAM J. Comput. 2013). At the same time, arguably, most "natural" and efficiently usable polynomial-time algorithms rarely exceed a quadratic or cubic time bound. In this paper we revisit Maltsev constraints with this question in mind and find a $O(n^2 \cdot m)$ algorithm (for finite languages, for infinite languages we in addition need to take the total size of the instance into account). The main novel idea is to not attempt to improve the bottleneck in Bulatov and Dalmau (the Fix-Values procedure) but to avoid it altogether with a slightly more refined approach that allows us to search through a smaller space.

0.25

Discrete Temporal CSPs et al

cs.CC math.LO ·2026-10-15 ·Lukas Pieper
similarity 0.66
Abstract

We revisit the complexity classification of constraint satisfaction problems (CSPs) for first-order reducts of $(\mathbb{Z},<)$, established by Bodirsky, Martin, and Mottet in 2018. Following their approach, we give a self-contained proof of this classification, correcting several errors in the argument. We further show that, with the exception of cases arising from finite-domain CSPs, all tractable cases are solved by a well-known uniform algorithm, eliminating the need for the collection of ad-hoc algorithms used in the original paper. A central component of the proof allows the analysis to be restricted to first-order reducts of $(\mathbb{Z},<)$ that contain the successor relation. We substantially simplify this reduction and generalize the underlying construction. This generalization allows us to apply the same technique to first-order reducts of the triangular lattice graph and of infinite regular trees, yielding a complete complexity classification for these classes of structures, in particular a $\mathsf{P}$ versus $\mathsf{NP}$-complete dichotomy.

0.21

From Block Orthogonality to Decidability in Complex-Weighted Counting CSP

cs.CC ·2026-08-14 ·Chenghua Liu, Boning Meng
theory similarity 0.65
Abstract · 68 pages; revised proof and exposition, including a correction; Lean repository linked

In a landmark JACM paper recognized with the 2021 Gödel Prize, Cai and Chen established a complexity dichotomy for counting CSPs over arbitrary finite domains with algebraic complex weights. Their tractability criterion consists of three conditions on the infinite family of functions obtained from CSP instances by summing out some variables: the Block Orthogonality and Type Partition conditions, and a Mal'tsev polymorphism condition on support and row-equivalence relations. They left open whether this criterion is decidable from the finite set of constraint functions. We resolve this question by giving a total exact algorithm for every $q$-element domain ($q\ge 1$), with algebraic weights encoded exactly. We also prove that the Block Orthogonality condition implies the other two conditions, reducing the tractability criterion to a single structural property. We obtain similar decidability and structural results for Lin's tractability criterion for $\#\mathrm{CSP}^{d}$, where each variable occurs a multiple of $d$ times. Our method first shows that every failure of Block Orthogonality can be witnessed by a generated function of arity at most $q^2+1$. At each such arity, we reduce checking infinitely many generated functions to finitely many exact algebraic tests, using tensor products and a pinned extension of Young's all-instance isomorphism theorem. For the structural implication, we use powers of generated functions to control complex cancellation and construct functions whose supports encode row equivalence. These constructions yield the Type Partition and Mal'tsev polymorphism conditions.

0.10

Complexity of Deciding Existence of Maltsev Polymorphisms of Finite Relational Structures

cs.CC cs.LO ·2026-11-10 ·Dejan Delic, Ali Syed
similarity 0.64
Abstract

In this article, we show that the problem of deciding whether a finite relational structure $\mathbf{A}$ admits a Maltsev polymorphism is a computational problem, which can be solved in polynomial time. We provide a proof of this result by reducing the problem to deciding whether a binary relational structure, associated with $\mathbf{A}$ admits such a polymorphism. In our construction of such an algorithm, we make an extensive use of a property of binary relations, which is implied by the existence of a Maltsev polymorphism, the so-called rectangularity property.

0.21

A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions

cs.CC ·2026-11-05 ·Aditya Bandekar, Amatya Sharma, Santhoshini Velusamy
theory similarity 0.63
Abstract

We characterize the single-pass streaming space complexity of Boolean CSP satisfiability in the strict-turnstile model for every fixed constraint language $Γ$ of $k$-ary Boolean relations that is not trivially satisfiable. Constraints can be inserted or deleted with nonnegative multiplicities; satisfiability is decided for those remaining at the end. While Sharma and Velusamy [ESA 2026] characterized insertion-only complexity via non-redundancy (up to logarithmic factors), we show that strict-turnstile complexity is governed by the integer capturing degree. For $R\subseteq\{0,1\}^k$, let $d_R$ be the minimum degree of an integer-coefficient polynomial vanishing exactly on $R$ over the Boolean hypercube, and set $d_Γ=\max_{R\inΓ}d_R$. On polynomial-length streams, we obtain an $O_k(n^{d_Γ}\operatorname{polylog} n)$-space randomized algorithm and an $Ω_k(n^{d_Γ}/\log n)$ lower bound for all algorithms. Moreover, our algorithm outputs a sparse instance preserving every satisfying assignment. This yields, to our knowledge, the first insertion-only versus turnstile separation for streaming CSPs. It also differs from the Fourier-degree characterization of exact optimization by Kol, Paramonov, Saxena, and Yu [ITCS 2023]. For $k\ge3$, $k$-XOR with literals has three distinct space complexities: $\widetildeΘ(n)$ for insertion-only satisfiability, $\widetildeΘ(n^{\lceil k/2\rceil})$ for strict-turnstile satisfiability, and $\widetildeΘ(n^k)$ for exact optimization in either model.

0.15

Combinatorial optimization with bounded subdeterminants

cs.DS cs.DMmath.COmath.OC ·2026-11-09 ·Samuel Fiorini, J. Pascal Gollin, Tony Huynh, Simon Keil, O-joung Kwon +3 more
similarity 0.62
Abstract · 25 pages

We take a first step toward a broader study of classical combinatorial optimization problems through the maximum subdeterminants of their standard integer programming formulations, yielding new positive results for several famous (NP-hard) problems. An integer matrix is totally $Δ$-modular if every square submatrix has determinant of absolute value at most $Δ$. For every fixed $Δ$, it has been known that maximum clique, maximum stable set, and minimum vertex cover can be solved in polynomial time on instances for which the coefficient matrix of the natural formulation is totally $Δ$-modular. We extend this list by showing that the same holds for many other problems, including the weighted versions of maximum cut, the traveling salesman problem, feedback vertex set, odd cycle transversal, dominating set, max 2-sat, induced matching, and cluster vertex deletion, as well as for $k$-colorability and graph isomorphism. Our proofs reveal several new ways in which bounded subdeterminants impose combinatorial structure: they bound the size or maximum degree of the input graph, bound packings of cycles and other obstructions, or yield decompositions into tractable graph classes such as forests, chordal graphs, graphs of bounded treewidth, and graphs of bounded linear mim-width.

0.20

Polynomial-Factor Deterministic NP-Hardness for SVP in Every $\ell_p$ Norm with $p>2$

cs.CC ·2026-08-14 ·Isaac M Hair, Amit Sahai
theory similarity 0.62
Abstract

We prove that for every constant $2<p<\infty$, the shortest vector problem in the $\ell_p$ norm is NP-hard to approximate within a polynomial factor under a deterministic reduction. More precisely, for lattices of rank $M$, we obtain a factor of $M^\varepsilon$ for every constant $0<\varepsilon<\min\{(p-2)/(4p),1/8\}$. For $p=\infty$, the same holds for every constant $0<\varepsilon<1/8$. Our reduction adapts OpenAI's encoding of a satisfying assignment for the closest vector problem ("Ten Advances in Mathematics and Theoretical Computer Science"). The encoding has one block of coordinates for each evaluation of a polynomial, with one position for each possible value. We allow the entries in a block to be arbitrary field elements, which can cancel when we take weighted sums of powers of these values. We show that on an unsatisfiable formula, a nonzero codeword with small support must have many nonzero entries in each block it uses. Applying a Hadamard matrix to each block, as in a work by Hair and Sahai (STOC 2026), gives the gap in vector length. The main results of this paper were discovered by Codex / ChatGPT 5.6 Sol Ultra using harness components from the UCLA Moonshot Harness Project, in response to a general strategy suggested by the authors. See the end of the introduction for a discussion.

0.32

Tight Algorithms for Conservative Finite-Valued CSPs Parameterized by Treewidth

cs.DS cs.CC ·2026-11-12 ·Jakob Greilhuber, Dániel Marx, George Osipov, Marta Piecyk, Paweł Rzążewski +1 more
similarity 0.62
Abstract · The abstract has been truncated for arXiv

We consider valued constraint satisfaction problems (VCSPs) with a fixed finite domain $D$ and a fixed finite constraint language $Γ$, in the setting where $Γ$ contains all crisp unary constraints (called hard lists) and the remaining cost functions are finite-valued. We call such a language a finite-valued hard-list language. Let $c_Γ$ be the size of the largest set $S\subseteq D$ such that $Γ$ can express (using the usual VCSP closure operations) a binary disequality function on elements of $S$. Our main result tightly connects the complexity of the problem parameterized by treewidth to this value $c_Γ$. (1) The problem can be solved in time $(c_Γ)^{\mathsf{tw}} \cdot (|I| + |\mathcal{T}|)^{O(1)}$ when given an instance $I$ with a tree decomposition $\mathcal{T}$ of width $\mathsf{tw}$ of the primal graph of $I$. (2) If $c_Γ\geq 2$, there is no such algorithm solving the problem in time $(c_Γ- \varepsilon)^{\mathsf{tw}} \cdot (|I| + |\mathcal{T}|)^{O(1)}$ for any $\varepsilon > 0$, unless the Primal Treewidth SETH (and hence CNF-SETH) fails. In particular, this gives a far-reaching generalization of a similar result of Esmer et al. [ESA 2024] on the optimization version of list homomorphism for graphs.

0.23