Cores determine streaming difficulty of constraint problems
Cores Characterize the One-Pass Streaming Complexity of CSPs
Computational ComplexityDiscrete MathematicsData Structures and Algorithms
Summary
This paper looks at how hard it is to solve certain types of puzzle-like problems called constraint satisfaction problems (CSPs) when each part of the problem can only be seen once in a stream of data. The authors find exact measures that tell you when these problems are easy or hard to solve under different goals, like deciding if the puzzle can be perfectly solved or finding the best approximate solution. They use a key idea called the 'core' of a problem, which is a simpler piece that reveals how tricky the problem really is. Their methods work for all kinds of CSPs with limited memory and only one pass through the data.
What this means in practice
- •For streaming algorithm designers: Determine precisely how difficult certain CSP tasks are to solve in a single pass with limited memory, guiding algorithm choices.
- •For distributed system developers: Understand the memory and pass limitations for testing constrained rules in large distributed data streams, improving resource planning.
A theory result. No direct application yet.
Authors
Joshua Brakensiek, Aaron Putterman, Amatya Sharma, Santhoshini Velusamy
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.