Search for: All records

Abstract An ordering constraint satisfaction problem (OCSP) is defined by a family$$\mathcal F$$ $F$of predicates mapping permutations on$$\{1,\ldots,k\}$$ $\{1,\dots ,k\}$to$$\{0,1\}$$ $\{0,1\}$. An instance of ($$\mathcal F$$ $F$) onnvariables consists of a list of constraints, each consisting of a predicate from$$\mathcal F$$ $F$applied onkdistinct variables. The goal is to find an ordering of thenvariables that maximizes the number of constraints for which the induced ordering on thekvariables satisfies the predicate. OCSPs capture well-studied problems including ‘maximum acyclic subgraph’ () and “maximum betweenness”. In this work, we consider the task of approximating the maximum number of satisfiable constraints in the (single-pass) streaming setting, when an instance is presented as a stream of constraints. We show that for every$$\mathcal F$$ $F$, ($$\mathcal F$$ $F$) is approximation-resistant to o(n)-space streaming algorithms, i.e., algorithms using o(n) space cannot distinguish streams where almost every constraint is satisfiable from streams where no ordering beats the random ordering by a noticeable amount. This space bound is tight up to polylogarithmic factors. In the case of , our result shows that for every$$\epsilon>0$$ $ϵ>0$, is not$$(1/2+\epsilon)$$ $(1/2+ϵ)$-approximable in o(n) space. The previous best inapproximability result, due to Guruswami & Tao (2019), only ruled out 3/4-approximations in$$o(\sqrt n)$$ $o\left(\sqrt{n}\right)$space. Our results build on recent works of Chou et al. (2022b, 2024) who provide a tight, linear-space inapproximability theorem for a broad class of “standard” (i.e., non-ordering) constraint satisfaction problems (CSPs) over arbitrary (finite) alphabets. Our results are obtained by building a family of appropriate standard CSPs (one for every alphabet sizeq) from any given OCSP and applying their theorem to this family of CSPs. To convert the resulting hardness results for standard CSPs back to our OCSP, we show that the hard instances from this earlier theorem have the following “partition expansion” property with high probability: For every partition of thenvariables into small blocks, for most of the constraints, all variables are in distinct blocks. 

{"Abstract":["We consider random walks on "balanced multislices" of any "grid" that respects the "symmetries" of the grid, and show that a broad class of such walks are good spectral expanders. (A grid is a set of points of the form 𝒮ⁿ for finite 𝒮, and a balanced multi-slice is the subset that contains an equal number of coordinates taking every value in 𝒮. A walk respects symmetries if the probability of going from u = (u_1,…,u_n) to v = (v_1,…,v_n) is invariant under simultaneous permutations of the coordinates of u and v.) Our main theorem shows that, under some technical conditions, every such walk where a single step leads to an almost 𝒪(1)-wise independent distribution on the next state, conditioned on the previous state, satisfies a non-trivially small singular value bound.\r\nWe give two applications of our theorem to error-correcting codes: (1) We give an analog of the Ore-DeMillo-Lipton-Schwartz-Zippel lemma for polynomials, and junta-sums, over balanced multislices. (2) We also give a local list-correction algorithm for d-junta-sums mapping an arbitrary grid 𝒮ⁿ to an Abelian group, correcting from a near-optimal (1/|𝒮|^d - ε) fraction of errors for every ε > 0, where a d-junta-sum is a sum of (arbitrarily many) d-juntas (and a d-junta is a function that depends on only d of the n variables).\r\nOur proofs are obtained by exploring the representation theory of the symmetric group and merging it with some careful spectral analysis."]} 

Motivated by recent advances in locally testable codes and quantum LDPCs based on robust testability of tensor product codes, we explore the local testability of tensor products of (an abstraction of) algebraic geometry codes. Such codes are parameterized by, in addition to standard parameters such as block length n and dimension k, their genus g. We show that the tensor product of two algebraic geometry codes is robustly locally testable provided n = Ω((k+g)²). Apart from Reed-Solomon codes, this seems to be the first explicit family of two-wise tensor codes of high dual distance that is robustly locally testable by the natural test that measures the expected distance of a random row/column from the underlying code. 

Given a sequence of samples x_1, … , x_k promised to be drawn from one of two distributions X₀, X₁, a well-studied problem in statistics is to decide which distribution the samples are from. Information theoretically, the maximum advantage in distinguishing the two distributions given k samples is captured by the total variation distance between X₀^{⊗k} and X₁^{⊗k}. However, when we restrict our attention to efficient distinguishers (i.e., small circuits) of these two distributions, exactly characterizing the ability to distinguish X₀^{⊗k} and X₁^{⊗k} is more involved and less understood. In this work, we give a general way to reduce bounds on the computational indistinguishability of X₀ and X₁ to bounds on the information-theoretic indistinguishability of some specific, related variables X̃₀ and X̃₁. As a consequence, we prove a new, tight characterization of the number of samples k needed to efficiently distinguish X₀^{⊗k} and X₁^{⊗k} with constant advantage as k = Θ(d_H^{-2}(X̃₀, X̃₁)), which is the inverse of the squared Hellinger distance d_H between two distributions X̃₀ and X̃₁ that are computationally indistinguishable from X₀ and X₁. Likewise, our framework can be used to re-derive a result of Halevi and Rabin (TCC 2008) and Geier (TCC 2022), proving nearly-tight bounds on how computational indistinguishability scales with the number of samples for arbitrary product distributions. At the heart of our work is the use of the Multicalibration Theorem (Hébert-Johnson, Kim, Reingold, Rothblum 2018) in a way inspired by recent work of Casacuberta, Dwork, and Vadhan (STOC 2024). Multicalibration allows us to relate the computational indistinguishability of X₀, X₁ to the statistical indistinguishability of X̃₀, X̃₁ (for lower bounds on k) and construct explicit circuits to distinguish between X̃₀, X̃₁ and consequently X₀, X₁ (for upper bounds on k). 

{"Abstract":["The celebrated Ore-DeMillo-Lipton-Schwartz-Zippel (ODLSZ) lemma asserts that n-variate non-zero polynomial functions of degree d over a field 𝔽, are non-zero over any "grid" (points of the form Sⁿ for finite subset S ⊆ 𝔽) with probability at least max{|S|^{-d/(|S|-1)},1-d/|S|} over the choice of random point from the grid. In particular, over the Boolean cube (S = {0,1} ⊆ 𝔽), the lemma asserts non-zero polynomials are non-zero with probability at least 2^{-d}. In this work we extend the ODLSZ lemma optimally (up to lower-order terms) to "Boolean slices" i.e., points of Hamming weight exactly k. We show that non-zero polynomials on the slice are non-zero with probability (t/n)^{d}(1 - o_{n}(1)) where t = min{k,n-k} for every d ≤ k ≤ (n-d). As with the ODLSZ lemma, our results extend to polynomials over Abelian groups. This bound is tight upto the error term as evidenced by multilinear monomials of degree d, and it is also the case that some corrective term is necessary. A particularly interesting case is the "balanced slice" (k = n/2) where our lemma asserts that non-zero polynomials are non-zero with roughly the same probability on the slice as on the whole cube.\r\nThe behaviour of low-degree polynomials over Boolean slices has received much attention in recent years. However, the problem of proving a tight version of the ODLSZ lemma does not seem to have been considered before, except for a recent work of Amireddy, Behera, Paraashar, Srinivasan and Sudan (SODA 2025), who established a sub-optimal bound of approximately ((k/n)⋅ (1-(k/n)))^d using a proof similar to that of the standard ODLSZ lemma.\r\nWhile the statement of our result mimics that of the ODLSZ lemma, our proof is significantly more intricate and involves spectral reasoning which is employed to show that a natural way of embedding a copy of the Boolean cube inside a balanced Boolean slice is a good sampler."]} 

We study the problem of constructing hypergraph cut sparsifiers in the streaming model where a hypergraph on n vertices is revealed either via an arbitrary sequence of hyperedge insertions alone (insertion-only streaming model) or via an arbitrary sequence of hyperedge insertions and deletions (dynamic streaming model). For any ε ∈ (0,1), a (1 ± ε) hypergraph cut-sparsifier of a hypergraph H is a reweighted subgraph H' whose cut values approximate those of H to within a (1 ± ε) factor. Prior work shows that in the static setting, one can construct a (1 ± ε) hypergraph cut-sparsifier using Õ(nr/ε²) bits of space [Chen-Khanna-Nagda FOCS 2020], and in the setting of dynamic streams using Õ(nrlog m/ε²) bits of space [Khanna-Putterman-Sudan FOCS 2024]; here the Õ notation hides terms that are polylogarithmic in n, and we use m to denote the total number of hyperedges in the hypergraph. Up until now, the best known space complexity for insertion-only streams has been the same as that for the dynamic streams. This naturally poses the question of understanding the complexity of hypergraph sparsification in insertion-only streams. Perhaps surprisingly, in this work we show that in insertion-only streams, a (1 ± ε) cut-sparsifier can be computed in Õ(nr/ε²) bits of space, matching the complexity of the static setting. As a consequence, this also establishes an Ω(log m) factor separation between the space complexity of hypergraph cut sparsification in insertion-only streams and dynamic streams, as the latter is provably known to require Ω(nr log m) bits of space. To better explain this gap, we then show a more general result: namely, if the stream has at most k hyperedge deletions then Õ(n r log k/ε²) bits of space suffice for hypergraph cut sparsification. Thus the space complexity smoothly interpolates between the insertion-only regime (k = 0) and the fully dynamic regime (k = m). Our algorithmic results are driven by a key technical insight: once sufficiently many hyperedges have been inserted into the stream (relative to the number of allowed deletions), we can significantly reduce the underlying hypergraph by size by irrevocably contracting large subsets of vertices. Finally, we complement this result with an essentially matching lower bound of Ω(n r log(k/n)) bits, thus providing essentially a tight characterization of the space complexity for hypergraph cut-sparsification across a spectrum of streaming models. 

{"Abstract":["We initiate the study of spectral sparsification for instances of Constraint Satisfaction Problems (CSPs). In particular, we introduce a notion of the spectral energy of a fractional assignment for a Boolean CSP instance, and define a spectral sparsifier as a weighted subset of constraints that approximately preserves this energy for all fractional assignments. Our definition not only strengthens the combinatorial notion of a CSP sparsifier but also extends well-studied concepts such as spectral sparsifiers for graphs and hypergraphs.\r\nRecent work by Khanna, Putterman, and Sudan [SODA 2024] demonstrated near-linear sized combinatorial sparsifiers for a broad class of CSPs, which they term field-affine CSPs. Our main result is a polynomial-time algorithm that constructs a spectral CSP sparsifier of near-quadratic size for all field-affine CSPs. This class of CSPs includes graph (and hypergraph) cuts, XORs, and more generally, any predicate which can be written as P(x₁, … x_r) = 𝟏[∑ a_i x_i ≠ b mod p].\r\nBased on our notion of the spectral energy of a fractional assignment, we also define an analog of the second eigenvalue of a CSP instance. We then show an extension of Cheeger’s inequality for all even-arity XOR CSPs, showing that this second eigenvalue loosely captures the "expansion" of the underlying CSP. This extension specializes to the case of Cheeger’s inequality when all constraints are even XORs and thus gives a new generalization of this powerful inequality which converts the combinatorial notion of expansion to an analytic property.\r\nPerhaps the most important effect of spectral sparsification is that it has led to certifiable sparsifiers for graphs and hypergraphs. This aspect remains open in our case even for XOR CSPs since the eigenvalues we describe in our Cheeger inequality are not known to be efficiently computable. Computing this efficiently, and/or finding other ways to certifiably sparsify CSPs are open questions emerging from our work. Another important open question is determining which classes of CSPs have near-linear size spectral sparsifiers."]}