PaperlayerView exact revision on arXiv

Source-linked AI summary

Cores Characterize the One-Pass Streaming Complexity of CSPs

Joshua Brakensiek, Aaron Putterman, Amatya Sharma, Santhoshini Velusamy

arXiv:2610.07455v1cs.CCcs.DMcs.DS

TL;DR

Prior streaming work left general-domain CSP characterizations unresolved, particularly where literal-based techniques do not extend. This paper reduces relations to their cores and uses that structure to characterize three one-pass objectives. The resulting parameters are core non-redundancy for satisfiability and minimization, and core indicator degree for exact optimization.

  • Problem

    For CSPs over arbitrary finite domains without literals, existing satisfiability techniques faced extension obstacles, while the broader streaming picture for the objectives studied remained incomplete.

    Source: §1 · pp. 3–4

  • Method

    The paper reduces each relation to its core, using homomorphisms and core gadgets that simulate variable pinning up to unavoidable symmetries.

    Source: §1.1 · p. 5, §2 · p. 6

  • Results

    After core reduction, non-redundancy characterizes SAT and Min-CSP up to polylogarithmic factors, while core indicator degree characterizes Exact-CSP up to a logarithmic factor.

    Source: §1 · p. 4

  • Takeaways & Limitations

    The core provides a shared structural basis for extending streaming lower-bound techniques to general finite-domain CSPs and determining the governing parameter for each objective.

    Source: §1 · p. 4, §1.1 · p. 5

    Whether the SAT and Min-CSP algorithms can be made efficient in both space and time remains open, partly because no general efficient technique for detecting non-redundancy is known.

    Source: §8 · p. 31

Abstract

from arXiv · show

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.

1 Introduction

The introduction asks how to characterize one-pass streaming complexity for CSPs without relying on literals, and presents core reduction as a route to tight results for three objectives. After reducing to the core, non-redundancy governs satisfiability and minimization, while indicator-polynomial degree governs exact optimization.

1 Introduction

  • Prior streaming characterizations for satisfiability relied on literals, whose gadget role obstructs extending those techniques to general finite domains.The paper notes that raw non-redundancy need not predict satisfiability complexity over domains larger than two.Source: §1 · p. 4
  • The core is a canonical reduction that removes domain values collapsible without changing the objectives, and the paper applies CSP cores to streaming complexity.The authors identify their work as the first use of CSP cores in this context.Source: §1 · p. 4
  • The paper studies SAT, approximate Min-CSP, and exact computation of the maximum number of satisfied constraints over finite-domain CSPs.These are distinct objectives: deciding whether all constraints can be satisfied, minimizing unsatisfied constraints, and computing the maximum satisfied count exactly.Source: §1 · p. 4

1.1 Our Results

  • For every fixed non-trivial relation R, SAT(R) has deterministic one-pass space O_R(NRD_n(core(R)) log n), with randomized lower bound Ω_R(NRD_n(core(R))).The upper and lower bounds are stated in Theorem 1.1.Source: §1.1 · p. 4
  • For every fixed non-trivial relation R and ε > 0, a deterministic one-pass (1 + ε)-approximation for Min-CSP(R) uses O_R,ε(NRD_n(core(R)) poly(log n)) space; every finite-factor randomized approximation needs Ω_R(NRD_n(core(R))) space.The paper obtains the minimization result from a sparsifier that preserves unsatisfied-constraint counts across assignments.Source: §1.1 · p. 5
  • Exact-CSP space complexity is determined by the degree of the core relation's indicator function.The paper states a logarithmic-factor characterization after reduction to the core.Source: §1.1 · p. 5
  • After reduction to the core, non-redundancy characterizes satisfiability and minimization up to polylogarithmic factors, while degree characterizes Exact-CSP up to a logarithmic factor.The paper's results cover unweighted CSP instances over arbitrary finite domains.Source: §1 · p. 4, §1.1 · p. 5

AI Disclosure.

The authors report using generative AI tools for language editing, exposition checks, routine mathematical tasks, and proof verification, but not to generate mathematical results or proofs.

AI Disclosure.

  • Generative AI tools assisted with language editing, exposition, routine mathematical tasks, and proof verification, but not with generating mathematical results or proofs.The authors state that they take full responsibility for the paper's contents.Source: AI Disclosure · p. 6

2 Technical overview

The overview reduces each relation to its core and uses core-specific gadgets to simulate variable pinnings for streaming lower bounds, with different pinning conditions for satisfiability and exact optimization. This core viewpoint explains earlier CSP characterizations and extends exact-optimization results to arbitrary finite-domain relations without literals or constants.

2.1 Reduction to the core

  • Replacing each constraint by its core-relation constraint preserves satisfiability, minimum unsatisfied constraints, maximum satisfied constraints, and one-pass streaming space.For the example relation T, NRD_n(T) = Θ(n^2) although satisfiability is decidable in O(n log n) space; core(T) = CUT has NRD_n(CUT) = Θ(n).Source: §2.1 · p. 7

2.2 Satisfiability and hard pinning

  • For core relations, automorphism-symmetric hard pinning turns INDEX into a satisfiability lower bound of Ω_R(NRD_n(R)) space.The gadget restricts assignments on the original variables to automorphic images of the desired assignment; each such image preserves which constraints are satisfied.Source: §2.2 · pp. 8–9

2.3 Exact-CSP

  • For a core relation of indicator degree d, Exact-CSP uses O(n^d log n) space and requires Ω_R(n^d) space up to a logarithmic factor.The upper bound stores coefficients of the low-degree polynomial for the instance; the lower bound combines 2^d point evaluations using strong pinning gadgets that make deviations unprofitable.Source: §2.3 · pp. 9–12
  • The strong-pinning lemma constructs H_s so OPT_max(P ∪ H_s) = |H_s| + val_P(s), even when P’s constraints are unknown during construction.For CUT, large blocks ensure every optimum follows the target assignment up to complementation; for general core relations, blocks enforce a common automorphism.Source: §2.3 · p. 11

2.4 Relation to prior work

  • Sharma and Velusamy [SV26a] characterized satisfiability with literals over finite domains and positive Boolean CSPs under a non-constant-satisfiable condition.With literals, variable occurrences may be shifted modulo the domain; for positive Boolean CSPs, the condition excludes a constant assignment satisfying every relation.Source: §2.4 · p. 12
  • The core viewpoint recovers earlier results: reducing shift-closed literal languages preserves non-redundancy, while a Boolean language is a core exactly when it is not constant-satisfiable.Treating each shifted relation as separate makes the literal language shift-closed; on the Boolean domain, the only non-bijective maps are constant maps.Source: §2.4 · p. 12
  • The work gives a core characterization in the most general finite-domain setting.Precise statements and proofs are in Section A.Source: §2.4 · p. 12
  • Unlike Kol, Paramonov, Saxena, and Yu, whose characterization is limited to Boolean CSPs with literals and constants, this exact-optimization result covers arbitrary relations without either.Their lower bound extends to a constant number of passes; extending this work to multiple passes is identified as future work.Source: §2.4 · p. 12

3 Preliminaries

This section sets the finite-domain CSP model and its three objectives, then introduces the parameters and tools used to study one-pass streaming space.

3.1 CSPs

  • An ordinary R-constraint applies a fixed relation to an ordered tuple of variables, with repetitions allowed; instances may contain repeated constraints.For CUT, each constraint requires its two variables to differ, so a CUT-instance represents a graph.Source: §3.1 · p. 13

3.2 Objectives and streaming space

  • SAT asks whether all constraints can be satisfied, Min-CSP minimizes unsatisfied constraints, and Exact-CSP computes the maximum satisfied constraints.In the one-pass model, constraints arrive in arbitrary order, and the algorithm's stored bits measure space.Source: §3.2 · pp. 13–14

3.3 Non-redundancy

  • NRD_n(R) is the maximum number of constraints in an instance on at most n variables where each constraint has a witness violating only it.Every non-trivial fixed relation has NRD_n(R) = Ω_R(n).Source: §3.3 · p. 14

3.4 Cores, automorphisms, and hard pinnings

  • The core relation is obtained on the image of an idempotent endomorphism, and every endomorphism of that core is an automorphism.For Rstar, the core is CUT on {0, 1}.Source: §3.4 · p. 15

3.5 Finite-domain degree

  • The degree of a relation is the degree of its indicator function, defined through a finite-domain basis of coordinate-value indicators.Changing the chosen basepoint changes coefficients but not the degree.Source: §3.5 · pp. 15–16

3.6 Communication complexity

  • For lower bounds, Alice streams constraints encoding her INDEX string and sends the algorithm's memory state; Bob appends constraints determined by his index.Any s-space streaming algorithm yields a one-way protocol using s bits, and the reductions use randomized INDEX lower bounds.Source: §3.6 · p. 16

4 Properties of Cores

The paper reduces CSP objectives to a core relation without changing their optimum values or satisfiability. Core relations also support hard-pinning gadgets: one tolerates a common automorphism for satisfiability, while exact optimization requires a stronger gadget that penalizes deviations.

4 Properties of Cores

  • Applying one automorphism to every assigned value preserves the number of satisfied and unsatisfied constraints.This invariance makes a common automorphism harmless for objectives that depend only on these values.Source: §4 · p. 17

4.1 Reduction to the core

  • Replacing each constraint by its core-relation constraint on the same scope preserves both optimum values and satisfiability, as well as stream order and instance structure.The reductions preserve the number of variables and constraints, simplicity, and symmetry when the original relation is symmetric.Source: §4.1 · p. 17

4.2 Hard pinnings in a core relation

  • For satisfiability, a core-relation gadget pins variables to a chosen assignment up to one common automorphism.The construction uses O_R(1) extra variables and O_R(|X| + 1) constraints; satisfying assignments restrict to σ ◦ s for σ ∈ Aut(R).Source: §4.2 · pp. 18–19

4.3 Pinning for exact optimization

  • Exact optimization needs stronger pinning because violating gadget constraints can otherwise be offset by gains in the original instance.The strengthened construction uses blocks of variables representing domain values; deviations lose more gadget constraints than they can gain in the original instance.Source: §4.2 · p. 19, §4.3 · p. 19
  • The exact-optimization gadget yields the intended optimum while allowing a common automorphism, by making every other disagreement with the target lose more gadget constraints than it can gain.Its unweighted construction uses O_R(N) additional variables and is built independently of the constraints of the input instance.Source: §4.3 · pp. 19–20

5 Satisfiability

For satisfiability, the streaming space complexity is characterized up to a logarithmic factor by the non-redundancy of the core relation. A deterministic upper bound and a randomized lower bound match at this scale.

5 Satisfiability

  • SAT(R) has a deterministic one-pass upper bound O_R(NRD_n(core(R)) log n) and a randomized one-pass lower bound Ω_R(NRD_n(core(R))).The core reduction transfers both bounds to arbitrary fixed non-trivial relations.Source: §5 · p. 21, §5.1 · pp. 21–22
  • The upper-bound algorithm maintains a nonredundant subinstance with exactly the same satisfying assignments as the stream prefix.It adds each arriving constraint and removes constraints whose deletion does not change the satisfying assignments; the stored instance has at most NRD_n(R) constraints.Source: §5 · p. 21

5.1 Lower bound for a core relation

  • The lower bound encodes INDEX using a maximum nonredundant instance, with hard pinning letting Bob test the witness for his queried constraint.The pinned instance is satisfiable exactly when the queried constraint was not streamed, yielding an Ω(NRD_n(R)) randomized space bound.Source: §5.1 · pp. 21–22
  • Removing a constant number of variables preserves non-redundancy up to a relation-dependent constant factor, allowing the lower-bound construction to fit its pinning variables.A random choice of n − c_R variables retains Ω_R(NRD_n(R)) constraints with their witnesses.Source: §5.1 · p. 22

6 Sparsification and Min-CSP

The paper gives a one-pass sparsifier that preserves every assignment’s unsatisfied-constraint count within a multiplicative error, yielding a deterministic approximation algorithm for Min-CSP. Finite-factor randomized approximation also requires space at least on the scale of the core’s non-redundancy.

6 Sparsification and Min-CSP

  • A deterministic one-pass algorithm stores a weighted subinstance preserving every assignment’s unsatisfied-constraint count within 1 ± ε, using O_R,ε(NRD_n(R) polylog(n, m, 1/ε)) space.The resulting sparsifier supports the paper’s deterministic one-pass (1 + ε)-approximation for Min-CSP(R).Source: §6 · pp. 22–23

6.1 Sparsification

  • The sparsifier is built by repeatedly merging level-based summaries and sparsifying their weighted union, with multiplicative error bounds maintained across levels.The final union of the occupied-level sparsifiers approximates the entire input for every assignment.Source: §6.1 · p. 24
  • The sparsification framework uses deterministic reductions, reads the input stream once, and does not require advance knowledge of its length.Subsequent reductions operate only on stored sparsifiers, and the error schedule depends on the level.Source: §6.1 · p. 26
  • Finite-factor randomized one-pass approximation for Min-CSP requires Ω_R(NRD_n(core(R))) space.Any such approximation must distinguish zero from positive minimum unsatisfied value and therefore decides satisfiability.Source: §6.1 · p. 27

7 Exact-CSP

For Exact-CSP, the degree of the core relation governs one-pass space: a deterministic upper bound and randomized lower bound match up to a logarithmic factor on unweighted simple instances. The upper bound stores a low-degree representation, while the lower bound reduces from INDEX using signed assignment values and hard-pinning.

7 Exact-CSP

  • Reducing R to core(R) makes the core-indicator degree govern complexity up to the upper-bound logarithmic factor; degree zero means the core relation is empty or full.The core reduction preserves the relevant streaming complexity and simplicity conditions.Source: §7 · p. 27, §7.1 · p. 31
  • For d = deg_C(1_R⋆) ≥ 1, Exact-CSP(R) has a deterministic one-pass algorithm using O(nd log(n + 1)) bits on unweighted simple instances, while every randomized bounded-error one-pass algorithm there uses Ω_R(nd) bits.Source: §7 · p. 27
  • A degree-d representation of the core relation’s indicator lets the algorithm accumulate coefficients for products involving at most d variables, using O(nd(log n + log m)) bits.On simple instances, m is at most nk, giving O(nd log n) space.Source: §7 · pp. 27–28
  • After streaming, the algorithm evaluates its stored representation on every assignment and returns the maximum; post-stream computation time is unrestricted.The maximum for the core instance equals the optimum for the original relation.Source: §7 · p. 28

7.1 Lower bound for a core relation

  • For symmetric R with d ≥ 1, the Ω_R(nd) randomized lower bound still holds when no unordered scope is repeated.The reduction constructs constraints with distinct unordered scopes.Source: §7 · p. 27, §7.1 · pp. 28, 30
  • The lower bound reduces from INDEX_Nd: signed sums over 2^d assignments isolate a queried constraint while canceling every other constraint.Hard-pinning gadgets let the optimum reveal each selected assignment’s value.Source: §7.1 · pp. 29–31
  • The reduction to the core preserves simple instances, and for symmetric relations it also preserves unordered scopes.Thus the core-relation bounds extend to arbitrary R.Source: §7.1 · p. 31

8 Conclusion and Open Questions

The paper identifies relation cores as important to streaming-complexity characterizations for CSP optimization. It leaves open efficient implementations of two algorithms and the effect of allowing deletions.

8 Conclusion and Open Questions

  • The paper concludes that relation cores are vital for characterizing streaming complexity in CSP optimization problems.It calls for further study of the relationship between CSP cores and streaming complexity.Source: §8 · p. 31
  • Whether the satisfiability and minimization algorithms can be made efficient in both space and time remains open; efficiently detecting non-redundant instances is a key challenge.The passage says there is no general technique for that detection and links it to CSP kernelization.Source: §8 · p. 31
  • The paper considers insertion-only streams and leaves open what changes when deletions are allowed.Source: §8 · p. 31

A Literals and Non-Constant-Satisfiable CSPs

This section relates the general core characterization to earlier satisfiability results for CSPs with literals and for positive Boolean languages. It states the relevant core criterion for the latter.

A Literals and Non-Constant-Satisfiable CSPs

  • The section shows that the general core characterization recovers Sharma and Velusamy’s result for CSPs with literals.It does so by showing that passing the shift/sign-closed language to its core does not change non-redundancy.Source: A Literals and… · p. 35
  • For positive Boolean constraint languages, the section states that being a core is equivalent to not being constant-satisfiable.Source: A Literals and… · p. 35
  • For a finite constraint language, a core is one whose endomorphisms are all automorphisms; its core is obtained by restricting relations to a minimum-image endomorphism’s image.Source: A Literals and… · p. 35

A.1 Literal CSPs as a special case

The appendix recovers the earlier literal-CSP satisfiability characterization by viewing literal constraints as positive constraints over a shift-closed language. Its key step shows that core reduction preserves non-redundancy for such languages.

A.1 Literal CSPs as a special case

  • In the literal model over Z_q, each coordinate of a constraint may receive an arbitrary additive shift, so literals correspond to positive constraints over the shift closure.Source: §A.1 · pp. 35–36
  • For a shift-closed finite language, the core reduction preserves the largest size of a nonredundant instance, as witnessed by satisfaction-preserving maps in both directions.The proof constructs the core domain from representatives of cosets of shifts invisible to every relation.Source: §A.1 · pp. 36–37
  • The core map is an endomorphism: each relation maps to its restricted core relation, and the relation map is injective.Source: §A.1 · pp. 36–37
  • Applying the shift-closed-language result to the literal model recovers the prior one-pass satisfiability characterization for CSPs with literals.Source: §A.1 · p. 37

A.2 Non-constant-satisfiable Boolean CSPs

For Boolean constraint languages with nonempty relations, being a core is equivalent to not being constant-satisfiable. This equivalence lets the general core characterization recover the positive Boolean result of Sharma and Velusamy.

A.2 Non-constant-satisfiable Boolean CSPs

  • A language is constant-satisfiable when one Boolean value, assigned to every variable, satisfies every positive instance over it.Equivalently, the constant tuple for that value belongs to every relation in the language.Source: §A.2 · p. 37
  • For Boolean constraint languages with nonempty relations, being a core is equivalent to not being constant-satisfiable.Source: §A.2 · p. 37
  • The equivalence follows because every non-bijective Boolean map is constant, and such a map is an endomorphism exactly when its value's constant tuple belongs to every relation.Source: §A.2 · p. 37
  • Every non-constant-satisfiable Boolean constraint language is already a core, so the general characterization recovers Sharma and Velusamy's positive Boolean result.Source: §A.2 · p. 37
Loading 2610.07455v1…