CS Paper Radar

Cores Characterize the One-Pass Streaming Complexity of CSPs

Joshua Brakensiek, Aaron Putterman, Amatya Sharma, Santhoshini Velusamy

cs.CC cs.DMcs.DS ·submitted 2026-10-05 22:04 UTC · v1

Abstract

We study the one-pass streaming complexity of CSPs over a fixed finite relation $R$ under three natural objectives: $\textsf{SAT}(R)$, deciding whether all constraints can be satisfied; $\textsf{Min}$-$\textsf{CSP}(R)$, approximately minimizing the number of unsatisfied constraints; and $\textsf{Exact-CSP}(R)$, exactly computing the maximum number of satisfied constraints. Sharma and Velusamy (ESA 2026) characterized the streaming complexity of satisfiability for CSPs with literals using the non-redundancy parameter $\textsf{NRD}_n(R)$, which roughly measures the largest instance in which every constraint is independently necessary. For the most general setting without literals, they obtained the corresponding characterization for Boolean relations and showed obstacles to extending their techniques to larger domains. Kol, Paramonov, Saxena, and Yu (ITCS 2023) similarly characterized the streaming complexity of $\textsf{Exact-CSP}(R)$ for Boolean CSPs with literals in terms of the degree deg$(R)$ of the relation when written as a polynomial, while without literals, the corresponding result was known only for $\textsf{Max-Cut}$. For all three of the objectives we study, we give tight characterizations for unweighted CSP instances over arbitrary finite domains. The streaming algorithms we provide are deterministic, while the corresponding bounds are tight up to polylogarithmic factors, even against randomized algorithms. The central idea in all three results is a reduction of $R$ to its core, a canonical subrelation of $R$ which admits gadgets that allow for the hard-pinning (or fixing) of variables.

Closest papers

Nearest neighbours by meaning across the whole index.

Min-CSPs on Complete Instances III: Nearly Optimal Characterizations of Approximation for Symmetric CSPs

cs.DS ·2026-11-10 ·Yihwan Chae, Chenglin Fan, Donghyeon Lee, Euiwoong Lee
similarity 0.77
Abstract · 45 pages. Adjusted the placement of Table 1

This paper studies complete Min-$k$-CSPs: an instance on $n$ variables has one nontrivial constraint for every $k$-set of variables (so $\binom{n}{k}$ constraints in total), and the goal is to find an assignment that minimizes the number of unsatisfied constraints. They are motivated by the connections to machine learning and data science, as well as the possibility of being testbeds for new algorithmic techniques. Previous recent results presented polynomial-time algorithms for the decision version of every complete Boolean $k$-CSP, which is a necessary condition for any multiplicative approximations for the minimization version, but nontrivial approximation results have been limited to fragile CSPs, 2-SAT, and NAE-3-SAT, leaving the approximability of most complete Boolean Min-CSPs open, including complete Min-$k$-SAT. In this paper, we resolve this question, up to nearly matching factors, for the natural class of symmetric Boolean predicates. Given $A \subseteq \{0, \dots, k\}$, Min-CSP($A$) is a Min-$k$-CSP where each constraint is specified by $k$ literals and is satisfied if the number of true literals belongs to $A$. Let $w(A)$ be the maximum number of consecutive integers in $A$. Our main results for complete Min-CSP($A$) are (1) a QPTAS for $w(A) \leq 2$ and (2) an $\widetilde{O}(n^{w(A)-3})$-approximation for $w(A) \geq 3$, as well as almost matching hardness results for the latter. Our QPTAS for $w(A)=2$ significantly improves the previous $O(1)$-approximation for Min-2-SAT and the $\operatorname{polylog}(n)$-approximation for Min-NAE-3-SAT, as well as extends the PTAS for fragile CSPs (i.e., $w(A) = 1$).

0.24

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.76
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

Upper Bounds for CSP Non-redundancy via Locally Decodable Codes

cs.DM cs.CCcs.ITmath.CO ·2026-10-28 ·Joshua Brakensiek, David Conlon, Venkatesan Guruswami, Xiaoyu He, Jiaxi Nie +2 more
similarity 0.73
Abstract · 24 pages

In the study of constraint satisfaction problems (CSPs), the non-redundancy of a relation measures the maximum number of clauses in a CSP instance which can be logically independent. In the last few years, CSP non-redundancy has found a number of applications including in query complexity, sparsification, kernelization and streaming. In this paper, we present a novel technique for upper-bounding the non-redundancy of some relations using locally decodable codes (LDCs) and locally correctable codes (LCCs). More precisely, known limitations on the structure of 2-query LDCs and LCCs can be translated into limitations on the size of certain non-redundant CSP instances. This technique builds on a technique used by Brakensiek and Guruswami [STOC 2025] to bound non-redundancy via techniques from matching vector codes. Using LDCs and LCCs, we give improved upper bounds on non-redundancy of the BCK predicate pioneered by Bessiere, Carbonnel, and Katsirelos [AAAI 2020] as well as its well-studied Boolean variant. We also give the first example of a Boolean predicate whose non-redundancy is provably not of the form $n^{k\pm o(1)}$ for some positive integer $k$.

0.12

Parameterized Approximation of Max k-Weight CSP: A Dichotomy for Boolean Languages

cs.DS ·2026-10-29 ·Rudranarayan Kar, Souvik Saha, Abhishek Sahu
similarity 0.68
Abstract

We study \textsc{Max $k$-Weight CSP}: maximize the satisfied weight of Boolean constraints with nonnegative rational weights by setting at most $k$ variables to $1$. Each constraint uses at most $d$ distinct variables and a relation from a finite Boolean language $Γ$. This includes \textsc{Partial Vertex Cover}, \textsc{Densest $k$-Subgraph}, bounded-frequency \textsc{Maximum Coverage}, and cardinality-constrained \textsc{Max-SAT}. We completely classify the fixed finite languages admitting an efficient parameterized approximation scheme (EPAS) with parameter $k+d$. Only nonempty relations excluding the all-zero tuple matter. For such a relation, a coordinate is a \emph{unit witness} if the tuple with a single $1$ in that coordinate is accepted, and a \emph{control} otherwise. A relation is \emph{Direct} if setting any selected control to $0$, with all other coordinates unchanged, preserves satisfaction. It is \emph{Rooted} if every satisfying tuple has a selected unit witness such that keeping it, setting all other unit witnesses to $0$, and setting any subset of selected controls to $0$ preserves satisfaction. If all such relations are Direct, or all are Rooted, we give a deterministic $(1-\varepsilon)$-approximation for every rational $\varepsilon\in(0,1)$ in time $2^{O(d+k\log(1+dk/\varepsilon))}\ell_{\mathrm{in}}^{O(1)}$, where $\ell_{\mathrm{in}}$ is the total input length. The algorithms are uniform in $d$ and give an EPAS parameterized by $k+d$ whenever relation membership is polynomial-time decidable. If neither condition holds, no EPAS exists unless $\mathsf{FPT}=\mathsf{W[1]}$, even for unweighted instances where no two constraints involve the same set of variables.

0.25

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.66
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.24

Stability Dichotomies for Boolean Constraint Satisfaction Problems

cs.DS ·2026-09-26 ·Chunyang Wang, Yuichi Yoshida
similarity 0.66
Abstract

We study the stability of Boolean constraint satisfaction problems (CSPs) through the notion of average sensitivity (Varma and Yoshida, SODA 2021; SICOMP 2023). It measures the expected $1$-Wasserstein distance between an algorithm's output distributions before and after the deletion of a uniformly chosen constraint, using the unnormalized Hamming metric. We establish two dichotomies for every finite Boolean constraint language $Γ$, where $n\geq 2$ denotes the number of variables in an instance. For stable solvability, exactly one of the following holds: $\bullet$ either there is an algorithm that solves $\mathrm{CSP}(Γ)$ and has average sensitivity $O_Γ(1)$ for all satisfiable instances; $\bullet$ or every algorithm that solves $\mathrm{CSP}(Γ)$ has average sensitivity $Ω_Γ(n)$ on satisfiable instances of arbitrarily large $n$. The first alternative holds if and only if $Γ$ has finite duality: unsatisfiability can be witnessed on a bounded number of variables. For stable approximability, where a $(1-\varepsilon)$-approximation violates at most an $\varepsilon$-fraction of the constraints in expectation, exactly one of the following holds: $\bullet$ either for every $\varepsilon\in(0,1]$, there is an algorithm that $(1-\varepsilon)$-approximates $\mathrm{CSP}(Γ)$ with average sensitivity $O_Γ(\varepsilon^{-1}\log n)$ for all satisfiable instances; $\bullet$ or there exists $\varepsilon_Γ\in(0,1]$ such that every algorithm that $(1-\varepsilon_Γ)$-approximates $\mathrm{CSP}(Γ)$ has average sensitivity $Ω_Γ(n)$ on satisfiable instances of arbitrarily large $n$. The first alternative holds if and only if $Γ$ has bounded width: local consistency checks on bounded sets of variables detect unsatisfiability.

0.31

An Improved Algorithm for Quantified Boolean Formulas

cs.DS cs.AI ·2026-11-07 ·Zhiyang Chen, Hailong Yao
similarity 0.66
Abstract

Quantified Boolean formula (QBF), the quantified version of Boolean satisfiability (SAT), is a fundamental problem in constraint solving. Due to the $\mathsf{PSPACE}$-complete nature of QBF, designing theoretically efficient QBF algorithms is much harder and receives less attention in academia. In this work, we present a new algorithm based on memoized search, which solves QBF with $n$ variables and $m$ clauses in $1.685^m\cdot\text{poly}(n)$ time and space. This is the first improvement over the $1.709^m\cdot\text{poly}(n)$ bound by Williams in over 20 years. Our technique is based on the minimum vertex cover of the conflict graphs, which was proposed to study the parameterized complexity of SAT. We extend this idea to QBF and further show that QBF is slicewise polynomial-time solvable using this parameter.

0.22

From Block Orthogonality to Decidability in Complex-Weighted Counting CSP

cs.CC ·2026-08-14 ·Chenghua Liu, Boning Meng
theory similarity 0.64
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