We identify a sharp separation in the streaming space complexity of Maximum Cut when the algorithm must output an approximate cut (rather than only the approximate value). For dense graphs, we show that O(n/ε²) space is sufficient and that Ω(n) space is necessary. In contrast, for graphs with Θ(n/ε²) edges, the situation is markedly different: we show that the problem requires Ω(n log(ε² n)/ε²) space for any ε = ω(1/√n), which is tight for the full range of ε. We also give an Ω(n log n/ε²)-space lower bound against deterministic algorithms for outputting a (1-ε) approximation to the value of the maximum cut. Using similar techniques we prove an analogous sharp separation in the streaming space complexity of Densest Subgraph and show that for every constant-arity CSP over a constant-size alphabet and the Similarity problem the space complexity in dense streams can be improved by shaving a logarithmic factor.

A recent work of Schmidhuber et al. (QIP, SODA, & Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted \(k\)xor problem running quartically faster than all known classical algorithms. In this work, we design a new classical algorithm that is quadratically faster than the best previous one, in the case of large constant \(k\). Thus for such \(k\), the quantum speedup of Schmidhuber et al. becomes only quadratic (though it retains a space advantage). Our algorithm, which also works in the semirandom case, combines tools from sublinear-time algorithms (essentially, the birthday paradox) and polynomial anticoncentration.

We explore the use of local algorithms in the design of streaming algorithms for the Maximum Directed Cut problem. Specifically, building on the local algorithm of (Buchbinder, Feldman, Seffi, and Schwartz [14] and Censor-Hillel, Levy, and Shachnai [16]), we develop streaming algorithms for both adversarially and randomly ordered streams that approximate the value of maximum directed cut in bounded-degree graphs. In n-vertex graphs, for adversarially ordered streams, our algorithm uses O (n1-Ω(1)) (sub-linear) space and for randomly ordered streams, our algorithm uses logarithmic space. Moreover, both algorithms require only one pass over the input stream. With a constant number of passes, we give a logarithmic-space algorithm which works even on graphs with unbounded degree on adversarially ordered streams. Our algorithms achieve any fixed constant approximation factor less than 1/2. In the single-pass setting, this is tight: known lower bounds show that obtaining any constant approximation factor greater than 1/2 is impossible without using linear space in adversarially ordered streams (Kapralov and Krachun [37]) and space in randomly ordered streams, even on bounded degree graphs (Kapralov, Khanna, and Sudan [35]).

Abstract An ordering constraint satisfaction problem (OCSP) is defined by a family $$\mathcal F$$ F of predicates mapping permutations on $$\{1,\ldots,k\}$$ {1,…,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(n) 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.

Motivated by recent works on streaming algorithms for constraint satisfaction problems (CSPs), we define and analyze oblivious algorithms for the Max-$k$AND problem. This generalizes the definition by Feige and Jozeph (Algorithmica '15) of oblivious algorithms for Max-DICUT, a special case of Max-$2$AND. Oblivious algorithms round each variable with probability depending only on a quantity called the variable's bias. For each oblivious algorithm, we design a so-called "factor-revealing linear program" (LP) which captures its worst-case instance, generalizing one of Feige and Jozeph for Max-DICUT. Then, departing from their work, we perform a fully explicit analysis of these (infinitely many!) LPs. In particular, we show that for all $k$, oblivious algorithms for Max-$k$AND provably outperform a special subclass of algorithms we call "superoblivious" algorithms. Our result has implications for streaming algorithms: Generalizing the result for Max-DICUT of Saxena, Singer, Sudan, and Velusamy (SODA'23), we prove that certain separation results hold between streaming models for infinitely many CSPs: for every $k$, $O(\log n)$-space sketching algorithms for Max-$k$AND known to be optimal in $o(\sqrt n)$-space can be beaten in (a) $O(\log n)$-space under a random-ordering assumption, and (b) $O(n^{1-1/k} D^{1/k})$ space under a maximum-degree-$D$ assumption. Even in the previously-known case of Max-DICUT, our analytic proof gives a fuller, computer-free picture of these separation results.

We give an $\widetilde{O}(\sqrt{n})$-space single-pass 0.483-approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on n vertices. This improves over an $O(\log n)$-space $4 / 9\lt 0.45$ approximation algorithm due to Chou, Golovnev, and Velusamy (FOCS 2020), which was known to be optimal for $o(\sqrt{n})$-space algorithms. Max-DICUT is a special case of a constraint satisfaction problem (CSP). In this broader context, we give the first CSP for which algorithms with $\widetilde{O}(\sqrt{n})$- space can provably outperform $o(\sqrt{n})$- space algorithms. The key technical contribution of our work is development of the notions of a first-order snapshot of a (directed) graph and of estimates of such snapshots. These snapshots can be used to simulate certain (non-streaming) Max-DICUT algorithms, including the “oblivious” algorithms introduced by Feige and Jozeph (Algorithmica, 2015), who showed that one such algorithm Previous work of the authors (SODA 2023) studied the restricted case of bounded-degree graphs, and observed that in this setting, it is straightforward to estimate the snapshot with $\ell_{1}$ errors and this suffices to simulate oblivious algorithms. But for unbounded-degree graphs, even defining an achievable and sufficient notion of estimation is subtle. We describe a new notion of snapshot estimation and prove its sufficiency using careful smoothing techniques, and then develop an algorithm which sketches such an estimate via a delicate process of intertwined vertex- and edge-subsampling. Prior to our work, the only streaming algorithms for any CSP on general instances were based on generalizations of the $O(\log n)$-space algorithm for Max-DICUT, and can roughly be characterized as based on “zeroth” order snapshots. Our work thus opens the possibility of a new class of algorithms for approximating CSPs by demonstrating that more sophisticated snapshots can outperform cruder ones in the case of Max-DICUT.

We initiate a study of the streaming complexity of constraint satisfaction problems (CSPs) when the constraints arrive in a random order. We show that there exists a CSP, namely Max-DICUT, for which random ordering makes a provable difference. Whereas a 4/9 ≈ 0.445 approximation of DICUT requires space with adversarial ordering, we show that with random ordering of constraints there exists a 0.483-approximation algorithm that only needs O(log n) space. We also give new algorithms for Max-DICUT in variants of the adversarial ordering setting. Specifically, we give a two-pass O(log n) space 0.483-approximation algorithm for general graphs and a single-pass space 0.483-approximation algorithm for bounded-degree graphs. On the negative side, we prove that CSPs where the satisfying assignments of the constraints support a one-wise independent distribution require -space for any non-trivial approximation, even when the constraints are randomly ordered. This was previously known only for adversarially ordered constraints. Extending the results to randomly ordered constraints requires switching the hard instances from a union of random matchings to simple Erdős-Renyi random (hyper)graphs and extending tools that can perform Fourier analysis on such instances. The only CSP to have been considered previously with random ordering is Max-CUT where the ordering is not known to change the approximability. Specifically it is known to be as hard to approximate with random ordering as with adversarial ordering, for space algorithms. Our results show a richer variety of possibilities and motivate further study of CSPs with randomly ordered constraints. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.07158. In this version, we omit many of the proofs.

A Boolean maximum constraint satisfaction problem, Max-CSP($f$), is specified by a predicate $f:\{-1,1\}^k\to\{0,1\}$. An $n$-variable instance of Max-CSP($f$) consists of a list of constraints, each of which applies $f$ to $k$ distinct literals drawn from the $n$ variables. For $k=2$, Chou, Golovnev, and Velusamy [CGV20, FOCS 2020] obtained explicit ratios characterizing the $\sqrt n$-space streaming approximability of every predicate. For $k \geq 3$, Chou, Golovnev, Sudan, and Velusamy [CGSV21, arXiv:2102.12351] proved a general dichotomy theorem for $\sqrt n$-space sketching algorithms: For every $f$, there exists $α(f)\in (0,1]$ such that for every $ε>0$, Max-CSP($f$) is $(α(f)-ε)$-approximable by an $O(\log n)$-space linear sketching algorithm, but $(α(f)+ε)$-approximation sketching algorithms require $Ω(\sqrt{n})$ space. In this work, we give closed-form expressions for the sketching approximation ratios of multiple families of symmetric Boolean functions. Letting $α'_k = 2^{-(k-1)} (1-k^{-2})^{(k-1)/2}$, we show that for odd $k \geq 3$, $α(k$AND$) = α'_k$, and for even $k \geq 2$, $α(k$AND$) = 2α'_{k+1}$. We also resolve the ratio for the "at-least-$(k-1)$-$1$'s" function for all even $k$; the "exactly-$\frac{k+1}2$-$1$'s" function for odd $k \in \{3,\ldots,51\}$; and fifteen other functions. We stress here that for general $f$, according to [CGSV21], closed-form expressions for $α(f)$ need not have existed a priori. Separately, for all threshold functions, we give optimal "bias-based" approximation algorithms generalizing [CGV20] while simplifying [CGSV21]. Finally, we investigate the $\sqrt n$-space streaming lower bounds in [CGSV21], and show that they are incomplete for $3$AND.

An ordering constraint satisfaction problem (OCSP) is given by a positive integer k and a constraint predicate Π mapping permutations on {1,…,k} to {0,1}. Given an instance of OCSP(Π) on n variables and m constraints, the goal is to find an ordering of the n variables that maximizes the number of constraints that are satisfied, where a constraint specifies a sequence of k distinct variables and the constraint is satisfied by an ordering on the n variables if the ordering induced on the k variables in the constraint satisfies Π. Ordering constraint satisfaction problems capture natural problems including "Maximum acyclic subgraph (MAS)" and "Betweenness". In this work we consider the task of approximating the maximum number of satisfiable constraints in the (single-pass) streaming setting, where an instance is presented as a stream of constraints. We show that for every Π, OCSP(Π) 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 MAS our result shows that for every ε > 0, MAS is not 1/2+ε-approximable in o(n) space. The previous best inapproximability result only ruled out a 3/4-approximation in o(√ n) space. Our results build on recent works of Chou, Golovnev, Sudan, Velingker, and Velusamy who show tight, linear-space inapproximability results for a broad class of (non-ordering) constraint satisfaction problems (CSPs) over arbitrary (finite) alphabets. Our results are obtained by building a family of appropriate CSPs (one for every q) from any given OCSP, and applying their work to this family of CSPs. To convert the resulting hardness results for CSPs back to our OCSP, we show that the hard instances from this earlier work have the following "small-set expansion" property: If the CSP instance is viewed as a hypergraph in the natural way, then for every partition of the hypergraph into small blocks most of the hyperedges are incident on vertices from distinct blocks. By exploiting this combinatorial property, in combination with the hardness results of the resulting families of CSPs, we give optimal inapproximability results for all OCSPs.