We study the single-pass streaming complexity of deciding satisfiability of Constraint Satisfaction Problems (CSPs). A CSP is specified by a constraint language Γ, that is, a finite set of k-ary relations over the domain [q] = {0, … , q-1}. An instance of CSP(Γ) consists of m constraints over n variables x₁, …, x_n taking values in [q]. Each constraint C_i is of the form {R_i,(x_{i_1} + λ_{i_1}, …, x_{i_k} + λ_{i_k})}, where R_i ∈ Γ and λ_{i_1}, …, λ_{i_k} ∈ [q] are constants; it is satisfied if and only if (x_{i_1} + λ_{i_1}, …, x_{i_k} + λ_{i_k}) ∈ R_i, where addition is modulo q. In the streaming model, constraints arrive one by one, and the goal is to determine, using minimum memory, whether there exists an assignment satisfying all constraints. For k-SAT, Vu (TCS 2024) proves an optimal Ω_k(n^k) space lower bound, while for general CSPs, Chou, Golovnev, Sudan, and Velusamy (JACM 2024) establish an Ω(n) lower bound; a complete characterization has remained open. We close this gap by showing that the single-pass streaming space complexity of CSP(Γ) is precisely governed by its non-redundancy, a structural parameter introduced by Bessiere, Carbonnel, and Katsirelos (AAAI 2020). The non-redundancy NRD_n(Γ) is the maximum number of constraints over n variables such that every constraint is non-redundant, i.e., omitting it strictly expands the set of satisfying assignments. We prove that the single-pass streaming complexity of CSP(Γ) is characterized, up to a logarithmic factor, by NRD_n(Γ). We also extend this characterization to positive Boolean CSPs, i.e., instances in which no additive shifts are applied, a class that includes graph 2-colorability (equivalently, bipartiteness) as a canonical example. A key ingredient in our lower bound proof is a binary relation ℰ on the set of assignments [q]ⁿ, where (a, b) ∈ ℰ if every instance satisfied by a is also satisfied by b. While it is immediate that ℰ is reflexive and transitive, its symmetry, which would make it an equivalence relation, is non-trivial. We show that ℰ is an equivalence relation for general CSPs, and for positive Boolean CSPs when excluding the two constant assignments (0ⁿ and 1ⁿ). We believe this equivalence structure could be of independent interest.

This paper studies complete k-Constraint Satisfaction Problems (CSPs), where an n-variable instance has exactly one nontrivial constraint for each subset of k variables, i.e., it has binom(n,k) constraints. A recent work started a systematic study of complete k-CSPs [Anand, Lee, Sharma, SODA'25], and showed a quasi-polynomial time algorithm that decides if there is an assignment satisfying all the constraints of any complete Boolean-alphabet k-CSP, algorithmically separating complete instances from dense instances. The tractability of this decision problem is necessary for any nontrivial (multiplicative) approximation for the minimization version, whose goal is to minimize the number of violated constraints. The same paper raised the question of whether it is possible to obtain nontrivial approximation algorithms for complete Min-k-CSPs with k ≥ 3. In this work, we make progress in this direction and show a quasi-polynomial time polylog(n)-approximation to Min-NAE-3-SAT on complete instances, which asks to minimize the number of 3-clauses where all the three literals equal the same bit. To the best of our knowledge, this is the first known example of a CSP whose decision version is NP-Hard in general (and dense) instances while admitting a polylog(n)-approximation in complete instances. Our algorithm presents a new iterative framework for rounding a solution from the Sherali-Adams hierarchy, where each iteration interleaves the two well-known rounding tools: the conditioning procedure, in order to "almost fix" many variables, and the thresholding procedure, in order to "completely fix" them. Finally, we improve the running time of the decision algorithms of Anand, Lee, and Sharma and show a simple algorithm that decides any complete Boolean-alphabet k-CSP in polynomial time.

Given a fixed arity k ≥ 2, MlN-k-CSP on complete instances is the problem whose input consists of a set of n variables V and one (nontrivial) constraint for every k-subset of variables (so there are constraints), and the goal is to find an assignment that minimizes the number of unsatisfied constraints. Unlike Max-k-CSP that admits a PTAS on more general dense or expanding instances, the approximability of Min-k-CSP has not been well understood. Moreover, for some CSPs including Min-k-SAT, there is an approximation-preserving reduction from general instances to dense and expanding instances, leaving complete instances as a unique family that may admit new algorithmic techniques.

In the Strip Packing (SP) problem, we are given a vertical half-strip \([0,W]\times[0,\infty)\) and a set of \( n \) axis-aligned rectangles of width at most \( W \) . The goal is to find a non-overlapping packing of all rectangles into the strip such that the height of the packing is minimized. A well-studied and frequently used practical constraint is to allow only those packings that are guillotine separable, i.e., every rectangle in the packing can be obtained by recursively applying a sequence of edge-to-edge axis-parallel cuts (guillotine cuts) that do not intersect any item of the solution. In this article, we study approximation algorithms for the Guillotine Strip Packing (GSP) problem, i.e., the SP problem where we require additionally that the packing needs to be guillotine separable. This problem generalizes the classical Bin Packing problem and also makespan minimization on identical machines, and thus it is already strongly \(\mathsf{NP}\) -hard. Moreover, due to a reduction from the Partition problem, it is \(\mathsf{NP}\) -hard to obtain a polynomial-time \((3/2-\varepsilon)\) -approximation algorithm for GSP for any \(\varepsilon > 0\) (exactly as SP ). We provide a matching polynomial time \((3/2+\varepsilon)\) -approximation algorithm for GSP. Furthermore, we present a pseudo-polynomial time \((1+\varepsilon)\) -approximation algorithm for GSP. This is surprising as it is \(\mathsf{NP}\) -hard to obtain a \((5/4-\varepsilon)\) -approximation algorithm for (general) SP in pseudo-polynomial time. Thus, our results essentially settle the approximability of GSP for both the polynomial and the pseudo-polynomial settings.

In two-dimensional geometric knapsack problem, we are given a set of n axis-aligned rectangular items and an axis-aligned square-shaped knapsack. Each item has integral width, integral height and an associated integral profit. The goal is to find a (non-overlapping axis-aligned) packing of a maximum profit subset of rectangles into the knapsack. A well-studied and frequently used constraint in practice is to allow only packings that are guillotine separable, i.e., every rectangle in the packing can be obtained by recursively applying a sequence of edge-to-edge axis-parallel cuts that do not intersect any item of the solution. In this paper we study approximation algorithms for the geometric knapsack problem under guillotine cut constraints. We present polynomial time (1+ε)-approximation algorithms for the cases with and without allowing rotations by 90 degrees, assuming that all input numeric data are polynomially bounded in n. In comparison, the best-known approximation factor for this setting is 3+ε [Jansen-Zhang, SODA 2004], even in the cardinality case where all items have the same profit. Our main technical contribution is a structural lemma which shows that any guillotine packing can be converted into another structured guillotine packing with almost the same profit. In this packing, each item is completely contained in one of a constant number of boxes and 𝖫-shaped regions, inside which the items are placed by a simple greedy routine. In particular, we provide a clean sufficient condition when such a packing obeys the guillotine cut constraints which might be useful for other settings where these constraints are imposed.