Streaming beyond sketching for Maximum Directed Cut

We give an $\widetilde{O}(\sqrt{n})$-space single-pass $0.483$-approximation streaming algorithm for estimating the maximum directed cut size ($\textsf{Max-DICUT}$) in a directed graph on $n$ vertices. This improves over an $O(\log n)$-space $4/9<0.45$ approximation algorithm due to Chou, Golovnev, Velusamy (FOCS 2020), which was known to be optimal for $o(\sqrt{n})$-space algorithms. $\textsf{Max-DICUT}$ is a special case of a constraint satisfaction problem (CSP). In this broader context, our work gives the first CSP for which algorithms with $\widetilde{O}(\sqrt{n})$ space can provably outperform $o(\sqrt{n})$-space algorithms on general instances. Previously, this was shown in the restricted case of bounded-degree graphs in a previous work of the authors (SODA 2023). Prior to that work, the only algorithms for any CSP were based on generalizations of the $O(\log n)$-space algorithm for $\textsf{Max-DICUT}$, and were in particular so-called"sketching"algorithms. In this work, we demonstrate that more sophisticated streaming algorithms can outperform these algorithms even on general instances. Our algorithm constructs a"snapshot"of the graph and then applies a result of Feige and Jozeph (Algorithmica, 2015) to approximately estimate the $\textsf{Max-DICUT}$ value from this snapshot. Constructing this snapshot is easy for bounded-degree graphs and the main contribution of our work is to construct this snapshot in the general setting. This involves some delicate sampling methods as well as a host of"continuity"results on the $\textsf{Max-DICUT}$ behaviour in graphs.


Introduction
We consider approximating the directed cut value of a directed graph by a streaming algorithm presented with a stream of edges in an arbitrary (worst-case) order. Our result is a single-pass algorithm using O( √ n)-space that gives a .483 approximation algorithm. In what follows we explain the background of this problem, the significance of the result, and the techniques used to achieve this result.

Background
We begin by defining the maximum directed cut (Max-DICUT) problem in a directed graph G.
(These definitions will all be informal; see Section 2 for formal definitions.) Given a graph G on n vertices, labeled 1, . . . , n, cut of G is a binary string x ∈ {0, 1} n , assigning a bit to every vertex in G. We say x cuts a directed edge (u, v) if x u = 1 and x v = 0. (Note the asymmetry between u and v.) The value val G (x) of a cut x is the total fraction of edges it cuts, and the value val G of G is the maximum value of any cut. A uniformly random cut has value 1 4 in expectation, so every graph has value at least 1 4 . We consider streaming algorithms for the problem of estimating the Max-DICUT value val G of a directed graph G, given a stream σ = (e 1 = (u 1 , v 1 ), . . . , e m = (u m , v m )) of the graph's edges in arbitrary order. We say an algorithm is an α-approximation for the Max-DICUT problem if its output v satisfies α · val G ≤ v ≤ val G (with high probability). We say an algorithm is a space-s(n) streaming algorithm (where n is the number of vertices in G) if it reads the stream of edges σ in sequential order and uses s(n) space.
The Max-DICUT problem is one example of a so-called constraint satisfaction problem (CSP). We omit a full definition as we do not require it, but these problems are basically defined by two things: (1) a "global" space of allowed "assignments" to "variables" and (2) a collection of "local" constraints, each of which specifies allowed values for a small subset of variables. For Max-DICUT, assignments are cuts, variables are vertices, and constraints are edges; we will use these terms interchangeably. The "symmetric version" of Max-DICUT is another CSP called maximum cut (Max-CUT), in which a cut x cuts an edge (u, v) if x u = x v ; we mention it here as it serves a useful point of comparison for Max-DICUT.
Max-DICUT has emerged as the central benchmark for algorithms among CSPs in the streaming setting. It was the first problem shown to admit a non-trivial approximation in sublinear (in n) space in the work of Guruswami, Velingker, and Velusamy [GVV17]. Subsequent work of Chou, Golovnev, and Velusamy [CGV20] gave an improved algorithm for Max-DICUT along with a tight bound on the approximability -pinning the approximability of Max-DICUT for o( √ n)-space streaming at 4 9 . Theorem 1.1 ( [CGV20]). For every ǫ > 0, there is a streaming algorithm (in fact, a linear sketching algorithm) which (4/9 − ǫ)-approximates the Max-DICUT value of a graph in O ǫ (log n) space. Conversely, every (4/9 + ǫ)-approximation streaming algorithm for Max-DICUT uses Ω ǫ ( √ n) space.
This result is part of a broader landscape for o( √ n)-space streaming complexity of CSPs. In particular, Chou, Golovnev, Sudan, and Velusamy [CGSV21] proved a dichotomy theorem for all finite CSPs. The understanding of Max-DICUT plays a central role in their results. In particular, they generalize the Max-DICUT algorithm of [CGV20] to all CSPs. Their lower bounds also generalize the lower bounds from [CGV20] with some notions ("padded one-wise independent problems") that are direct abstractions of Max-DICUT and share tight lower bounds. A sketching algorithm is a kind of streaming algorithm which chooses its output based on a short "sketch" of its input, where these sketches have the composability property that the sketch of a concatenation of two streams can be obtained from the sketches of the two components. (See [CGSV21] for a formal definition.) The algorithms of [GVV17,CGV20] for Max-DICUT were sketching algorithms and so were their generalizations in [CGSV21]. Our work is primarily motivated by the quest to look beyond sketching algorithms for streaming CSPs. One (over-)optimistic goal might be to find algorithms that outperform the current sketching algorithm for all CSPs.
But this hope is not achievable in sublinear space. For a wide class of CSPs, including Max-CUT, there are recent o(n)-space lower bounds ruling out all nontrivial approximations [KK19, CGS + 22b]. 12 Thus to make advances one has to restrict the problems considered and in this work we focus on the simplest remaining problem after Max-CUT, namely, Max-DICUT.
For Max-DICUT, till this work and a recent related work by the authors [SSSV23] it was conceivable that there were no improvements possible in o(n) space. But at the same time the above mentioned lower bounds did not extend to this setting and it was unclear whether this was due to a limitation of the lower bounds techniques or if better algorithms exist.
In a previous work [SSSV23], the authors gave some evidence for the possibility that better algorithms for Max-DICUT do indeed exist. To be precise, recall that the sketching algorithm of [CGV20] is a 4 9 ≈ 0.444-approximation, which uses O(log n) space and is optimal among o( √ n)space streaming algorithms (Theorem 1.1). In [SSSV23] we proved that for Max-DICUT, the algorithm of [CGV20] can be beaten in a number of restricted models such as when the input stream is randomly (instead of adversarially) ordered, or the graph has constant max-degree. In particular:  [CGV20] can be beaten on general graphs in o(n) space. Indeed, it could be considered evidence only that evenmore-sophisticated lower bound techniques are necessary to rule out such algorithms. We further discuss why we believe that Theorem 1.2 was far from an answer to this question in Section 1.4 below.

Main result
Our main theorem gives an algorithm that uses slightly more than √ n space and outperforms the algorithm of [CGV20]: This theorem is proven in a more precise formulation as Lemma 4.2 below.
1 o(n) space is tight up to logarithmic factors because randomly sparsifying down to O(n/ǫ 2 ) constraints gives (1 − ǫ)-approximations. 2 The condition for inapproximability given in [CGS + 22b] for a predicate f : Z k q → {0, 1} is termed "width", and states that f 's support contains some translate of the diagonal {(a, . . . , a) : a ∈ Z k q }. More broadly, the strongest known hardness results for CSPs (e.g., also in [CGSV21]) seem to rely on "niceness" properties of the support of f . Like the previous algorithms for Max-DICUT [GVV17, CGV20, SSSV23], our algorithm relies crucially on the notion of the bias of a vertex in a directed graph. Given a directed graph G and a (positive-degree) vertex v, we define the bias bias G (v) of v as the difference between its outand in-degrees divided by their sum. This is a number between −1 and 1 which represents v's "preference" for being assigned 1 vs. 0.
Earlier papers working in the O(log n)-space setting [GVV17, CGV20] measured a quantity called the total bias of G, namely bias G = 1 2m n v=1 deg G (v)|bias G (v)|, using standard ℓ 1 -norm sketching algorithms and used this as a proxy for the value of G. 3 The current work relies on measuring a so-called "snapshot" of the graph, which roughly says how many edges go from vertices of bias ≈ s to vertices of bias ≈ t, for every choice of s, t ∈ [−1, 1]. Plugging this snapshot into an algorithm due to Feige and Jozeph [FJ15] gives us our estimator for the Max-DICUT value. Thus the novelty of our algorithm is in producing the snapshot in roughly √ n space.
We remark that our algorithm is not a sketching algorithm, unlike all previously known algorithms for CSPs (in the standard model). We do not currently know that sketching algorithms cannot match the performance of our algorithm, but we also do not know a sketching algorithm that can.

Beyond bounded-degree instances
As mentioned above, our prior work [SSSV23] already achieves our main theorem for the special case of bounded-degree graphs. In this section we argue why the extension to the general case is non-trivial and important.
We start with considering the previous works of [ GVV17,CGV20,CGSV21]. The algorithms in all these works use powerful norm estimation algorithms as black boxes. If one were to consider the simpler case of their problems in the bounded-degree setting, these algorithms could have been implemented without reliance on these subroutines. The Max-DICUT algorithms only need an estimate of the absolute value of "bias times the degree" for a random vertex, and this could be estimated by simply picking a random sample of the vertices and computing their bias and degree as the stream passes by. For general CSPs (even on non-Boolean domains) also such a process would suffice, and this would not only simplify the algorithms significantly, it even would achieve a space bound of O(log n) which is better than the current bounds given in [CGSV21] for general CSPs.
Digging deeper into this analogy one can consider ℓ p norm estimation problems themselves. For this class of problems also one can define a bounded-degree version of the problem -where one is trying to compute the ℓ p norm of a vector in {−C, . . . , C} n in the turnstile update model. In this bounded-degree setting, the ℓ p norm can be trivially computed by randomly sampling an O C (1)sized subset of the coordinates and maintaining their values. Thus ℓ p norms can be estimated in O(log n) space for every p in this bounded-degree setting, whereas in the general case it is well-known that ℓ p norm estimation requires polynomial in n space for p > 2.
Thus, the bounded-degree setting can be vastly easier to solve and results in this setting may best be viewed as a proof of concept -though even this "proof of concept" may be misleading, as exemplified by the ℓ p norm estimation problem.
Turning to our specific goal -that of computing snapshots of a graph in O( √ n) time -our prior work [SSSV23] again manages to estimate this snapshot in the bounded-degree setting by 3 In other words, biasG averages the absolute difference between out-and in-degree over vertices in the graph. Intuitively, the larger biasG is, the more "opinionated" each vertex is and therefore the easier it is to find a high-value assignment; this is made quantitative in [GVV17,CGV20]. Note also that biasG is the ℓ1 norm of the vector of differences of out-and in-degrees, and each edge in the stream adds 1 to one entry and subtracts 1 from another.
sampling O( √ n) vertices and maintaining the bias of the sampled vertices as well as the induced subgraph on these vertices. We discuss why this is reasonable in the bounded-degree setting in the following subsection. But such a simple algorithm is definitely not going to work in the general setting! In particular, computing a good estimate of the snapshot is at least as hard as computing the ℓ 1 norm of a vector in the turnstile model with unit updates. Indeed, "snapshot" estimation seems to be a "higher-level" challenge than simple norm estimation and roughly requires computing some "two-wise" marginals of the graph updates, whereas bias corresponded to "one-wise" marginals. Black-box use of norm-estimation algorithms no longer seems to suffice to solve these "two-wise" marginal problems, which seem to need new algorithmic ideas. We feel this class of problems and the ideas used here to deal with them may be of even broader interest than the application to Max-DICUT.

Techniques: Streaming estimation of "snapshots"
In this section, we dive into the specific challenges arising in computing "snapshots" of graphs in the general setting. We also begin to describe our algorithm; we aim to progressively narrate and motivate its development as there are a number of technical issues which arise. The algorithm proper is described completely in Section 4. Roughly, the Feige-Jozeph algorithm [FJ15] can be viewed as a reduction from the problem of approximating the Max-DICUT value of a graph G to a problem of the form, Given a graph G and fixed s < s ′ , t < t ′ , estimate the number of edges More precisely, [FJ15] gives us some fixed partition t 0 = −1 < · · · < t ℓ = 1 of the space of possible biases. Given a graph G, we refer to all vertices v ∈ V (G) with bias in the interval [t i−1 , t i ) as bias class i. For a graph G, we let BiasMat G,t denote the ℓ × ℓ matrix whose (i, j)-th entry counts the fraction of edges in G from bias class i to bias class j. We refer to this matrix informally as a "bias snapshot" of G. We can use the algorithm of [FJ15] as a black box to approximate the Max-DICUT value of a graph G up to a factor 0.483, given an estimate for this snapshot matrix in ℓ 1 -norm (see Corollary 3.4 below).

Algorithms based on vertex-subsampling
Setting aside the streaming model momentarily, the most natural way to build a snapshot for general graphs is to sample O(log n) edges from G independently and uniformly at random, and measure the biases of their two endpoints. Using these computed values, one can then estimate the entries of the matrix BiasMat G,t and standard concentration inequalities will yield the required approximation to Max-DICUT. Unfortunately, in the streaming setting when the edges are adversarially ordered there is no obvious way to implement the above sampling procedure since by the time the "random" edge appears in our stream, most of the edges incident to the endpoints might have already appeared, and thus, we may not know their biases. 4 Subsampling vertices independently. Another approach one might try is to track the bias of a subset S of vertices from the beginning of the stream and restrict attention to the edges in the subgraph induced by the vertices in S. If each vertex of G is included in S with probability, say, ρ = log m m so that the probability that an edge in G is in the induced subgraph is ρ 2 = log m m , sampling this way has the nice property that (like in the "ideal" case of directly sampling edges) the number of edges in the induced subgraph is O(log m). Moreover, as one only needs to store the bias of the vertices in S which are non-isolated in G and there are at most 2m non-isolated vertices in G (each of which is included in S with probability ρ), sampling this way requires space at most 2m · ρ = O( √ m). As m ≤ O ǫ (n), this is also O( √ n) and so fits within the space bound.
Unfortunately, sampling this way also means that the edges in the induced subgraph are no longer independent. Indeed, consider two edges e 1 and e 2 that share a common vertex v. If e 1 is in the induced subgraph, then v must be in S, increasing the chance that e 2 is also in the induced subgraph, and breaking the independence. Without the independence, we can no longer apply concentration inequalities and get an estimate for the Max-DICUT value of G. However, not all hope is lost, as two edges are independent only if they share a common endpoint, and e.g., if the graph has small maximum degree, then we can control the amount of dependence between edges and still make the argument successful. In fact, this is exactly what was done in the algorithm presented in [SSSV23] for graphs with small maximum degree (Theorem 1.2 above).
To be precise, the argument for correctness of the estimate in the bounded-degree case uses a form of Chebyshev's inequality (see Corollary 2.8). If we sample each vertex with probability p in a graph with maximum degree d, and our estimate an entry of BiasMat G,t will be within ǫm of the true value except with probability O(d/p 2 ǫ 2 m). So, the larger the maximum-degree d, the larger p must be to ensure correctness; ω( √ n) space is required even for d = n 0.01 .
Towards general graphs. How can we hope to extend this procedure to general graphs? Firstly, we observe that a standard sparsification argument shows that Max-DICUT algorithms for graphs with O(n/ǫ 2 ) edges lift to Max-DICUT algorithms for all graphs, with ǫ loss in the approximation factor (see Lemma 2.9 below). This lets us reduce to only considering graphs with O(n) edges.
Our goal is to build on the vertex sampling approach described above, and show that it can be extended to work for general graphs. For this, we first observe that the approach above works as is even if the graph does not have small maximum degree, as long as the degree of non-isolated vertices in G are "roughly the same". Indeed, if all the positive-degree vertices in G have degree, say, between d and 2d, one can subsample the edges of the graph independently with probability C/d for some large constant C; the resulting graph will, with high probability, have maximum degree O(C) and preserve the bias matrix BiasMat G,t up to additive (ℓ 1 -norm) errors. Then, one can apply the bounded-degree case from [SSSV23] and get a required approximation for the Max-DICUT of G.
The more challenging (and general) case is when the graph contains vertices with a wide range of different degrees. Roughly, the plan is to fix an ordered partition d = (d 1 , . . . , d k ) of the possible degrees in the graph G. Then, for each a ∈ {1, . . . , k} we aim to sample a set of vertices whose degree is "roughly" d a . To do so, we first subsample a graph G a ⊆ G by including each edge (randomly, independently) with probability q a = C/d a for some large constant C. Note that with high probability, vertices with degree roughly C in G a will correspond to vertices with degree roughly d a in G. The next step is to subsample the positive-degree vertices in G a by including each vertex (randomly, independently) with an appropriately chosen probability p a , and then use information about these vertices to try and estimate our snapshot.
The bias-degree array. It is no longer clear how we can directly estimate the bias matrix BiasMat G,t . Instead, we first focus on estimating the more complex array BiasDegArr G,d,t whose (a, b, i, j)-th entry contains the fraction of edges in G that go from vertices in bias class i and degree class 5 a to vertices in bias class j and degree class b. Note that this array is more granular than the matrix BiasMat G,t which we actually want to estimate -in particular, the matrix BiasMat G,t can be computed from the array BiasDegArr G,d,t by "projecting" it to its third and fourth coordinates -but this change is reasonable in our setting because the parameters for subsampling edges and vertices are heavily dependent on the degrees of vertices of interest. We will abbreviate A = BiasDegArr G,d,t for convenience and focus on computing (actually, estimating) A via a "subsampling strategy" like the above.

Estimating the array using edge-and vertex-subsampling
Fix some degree partition d = (d 1 , . . . , d k ) in which d a+1 /d a = O(1) for all a; we use d a+1 = 2d a (note that k = O(log n)). We think of each a ∈ [k] as a layer which targets vertices in degree class a, i.e., vertices with degree in the range (2 a−1 , 2 a ], and makes sure that these vertices have small maximum degree in the subsampled graph G a . This is done by sampling each edge in G independently with probability roughly 2 −a , and considering the graph G a consisting of the sampled edges. Then, we subsample a set S a of positive-degree vertices in G a . Given an edge which is somehow sampled in this kind of procedure, we will want to know the bias (and degree) of its endpoints in order to add it into the appropriate entry of A. In general, when a vertex shows up in the stream for a subsampled graph G a many of its incident edges in the base graph G may have slipped by! However, we can use the bias and degree of a vertex v ∈ S a within the subgraph G a as an estimate for the bias and degree, respectively, in the base graph G, as long as v's degree is "decently high". We mostly ignore this issue in this subsection, but it is quite important in the analysis and we discuss it in the next subsection.
Estimating edges within each layer. Consider the simple strategy where we just store the subgraph induced on S a within the graph G a . We can look at these induced subgraphs andmodulo the issue of estimating the bias and degree of sampled vertices -estimate, for all a ∈ [k], the entries of A corresponding to the edges going from vertices of degree class a to degree class a with bias classes i and j. However, this is only a small subset of the entries of A which we need to estimate. Given a = b ∈ [k], how can we estimate the "cross edges" between a and b?
Modifications for estimating cross edges. The above approach does not let us estimate the number of cross edges directly. To see why, fix a < b ∈ [k] and observe that vertices in degree class b are expected to have a high degree in layer a (as they are expected to have 2 b edges and we subsample with probability 2 −a ) while the vertices in degree class a are expected to have almost no edges in layer b. The former means that we cannot estimate the cross edges from the graph G a as it has high maximum degree, while the latter means that we cannot estimate the cross edges from the graph G b , as we lose almost all information about the biases and degrees of layer a.
In order to estimate the cross edges, we strengthen the sampling algorithm in the following two ways: 1. Firstly, when looking at the layer G a , in addition to the edges in the subgraph induced by the set of vertices S a sampled in this layer, we also remember all edges in G a that are incident on a vertex in S a whose degree class is a. As the algorithm does not know the degree class of any vertex a priori, this is actually implemented indirectly, namely, by remembering log O(1) n many edges from all vertices in S a . This "cutoff" number of edges is small enough to not increase the space used by a lot, but also large enough to allow all the edges of vertices in degree class a to be remembered (as these vertices are expected to have low degree in G a ).
2. Secondly, observe that as the layer a increases, the number of edges in G a decreases. By the calculation in Section 1.5.1, this means that the amount of memory required to remember the biases and degrees of the vertices in S a also decreases. As the number k of layers is small, we actually do not need this memory to decrease, and can actually afford to give all the layers the same memory as the first layer, namely O( √ n). By appropriately changing the parameters in the "higher" layers, this extra memory allows us to remember the biases of an even larger set S a , which will be useful in estimating the cross edges precisely.
How to estimate cross edges? We claim that, with these modifications, one can estimate cross edges between layers a and b by looking at the graph G a and counting the number of edges in this graph that go from vertices in S a to vertices in S b . To see why this works, we consider a = 1 and two cases for b: • When 2 b ≥ √ n: In this case, we claim that S b is sufficiently large as to contain all the vertices in G with degree class b. Indeed, as the the degree of such vertices is around 2 b ≥ √ n and the total number of edges in G is m ≤ O ǫ (n), the number of vertices in G with degree class b cannot be much larger than √ n. As explained in Item 2, this means that all these vertices will be in S b .
Given the fact that S b has all these vertices and we have Item 1, whether or not a cross edge e = (u, v), where u has degree class a and v has degree class b, is counted depends only on whether or not u ∈ S a and whether or not e ∈ G a . The latter is independent across all edges while the former has only a small amount of dependence, as the vertices in degree class a have low degree in G a , and does not harm the concentration inequalities too much.
• When 2 b < √ n: The argument above will not directly work in this case, as now whether or not a cross edge is counted also depends on whether or not v ∈ S b . As the vertices in degree class b have high degree in G a , this creates a lot of dependencies (depending on 2 b−a ) and breaks the concentration bounds.
What saves us here is that in Items 1 and 2, we sample all edges in G a that are incident on S a and also remember extra vertices in S b . Thus, the number of cross edges between a and b that are remembered in G a is much larger than O(log m) (which was the number obtained in the bounded-degree case). Having a larger number of cross edges also means we can also afford to deviate by more without affecting the multiplicative guarantee, and this larger deviation will help us deal with the extra dependencies in this case.

Windows, smoothing, and continuity
Even with the modifications above, there is a major problem that we still have to overcome. This problem arises because we do not compute the degrees and biases of the vertices in G exactly, and instead estimate them from the sampled graphs G a . These estimates will always be slightly off, and this can wreak havoc in the analysis, as the following example shows.
Consider an edge containing a vertex v with degree 2 a so that it is at the "boundary" of degree classes a and a + 1. (One could also consider a vertex with bias t i , which is at the boundary of bias classes i and i + 1, or a vertex that is at the boundary of both.) It is impossible to determine with high probability which entries of the estimate for A such an edge will contribute to -in some subsamples, the vertex could "appear to be" in degree class a and in others it could be in a + 1. Thus, we will end up counting this vertex in both the classes, making our estimates off by a factor of 2 for these vertices! Note that the vertices that are not at the boundary will only be counted in one class, and we cannot simply divide by 2 throughout to make this problem go away.
The solution we come up with is to use windows: Instead of trying to estimate entries of A individually, we group them into "windows" and estimate the average of all the entries in the window instead. For example, when trying to estimate the degree class a, we instead take a windowing parameter w and estimate the average of all degree classes {a − w, . . . , a + w} 6 . This mellows the problem of overestimating by a factor of 2 and makes it manageable: Now, every entry is overcounted 2w + 1 times and the boundary entries, in the worst case, will be over-counted at most 2(w + 1) + 1 times. As 2(w+1)+1 2w+1 ≈ 1 for large w, this is still manageable. However, we now need to show that we can rely on the algorithm of [FJ15] to compute a Max-DICUT value even if we only have windowed averages of A instead of A itself. This constitutes another major part of our analysis (see Section 3) where we essentially show that the value of Max-DICUT is "continuous" in the sense one can work with the weak "smoothed" estimates resulting from windows without losing out on the overall approximation factor. This part may be of independent interest.
Increasing the window size w Figure 1: A depiction of how larger windows reduce the "borderline" effects (in two dimensions). As w becomes larger and larger, a w × w rectangle (dark gray) dominates its "boundary" (light gray) more and more. Geometrically, a rectangle is two-dimensional while its boundary is "essentially one-dimensional". However, for estimating the Max-DICUT value in a graph, smoothing over size-w windows for large w introduces errors from the use of "continuity" results (i.e., Lemma 3.13 below). The right choice of w strikes a balance between these two forces.
Brief outline of Section 3. We have a few key lemmas about the windowing operation. Our key "continuity" lemma, Lemma 3.13 below, states that this operation preserves the Max-DICUT value of the graph in a precise sense, which may be of independent interest. We prove Lemma 3.13 constructively in Section 6.5 below, by "blowing up" each vertex into many copies and slightly tweaking the biases and degrees of each.
Separately, we also define a pair of arrays, which we denote A −w and A +w , which capture the "worst lower bound" and "worst upper bound", respectively, for the smoothed array A ∼w when allowing "off by one" errors for which entries count. In other words, each entry of A −w sums over a smaller surrounding window of width only w − 1, while entries of A +w sum over larger windows X A B C D Figure 2: Consider estimating a (two-dimensional) matrix with "off-by-one" errors, wherein the mass of each entry may shift to one of 8 neighboring entries (red boxes). If we estimate an average over a window of size w = 4 in taxicab distance around an entry X (green rectangle): (i) "Outer" entries, such as the one marked D, beyond distance w + 1 = 5 from the center (light gray) can never contribute. (ii) "Inner" entries, such as the one marked A, within distance at most w − 1 = 3 from the center (dark gray) always contribute. (iii) "Borderline" entries, such as B or C, may or may not contribute, depending on the specific error pattern.
and thus it makes sense to only aim for an estimate between A −w and A +w (as opposed to aiming directly for A ∼w ). We call such an estimate a "weak estimate" of A ∼w .
These lemmas in turn are the basis of our overall "reduction" lemma, Lemma 3.22, which gives a set of conditions on a "weak estimate" for A ∼w which are sufficient to guarantee that it can be plugged into the algorithm of Feige and Jozeph [FJ15] (with controlled loss in the approximation factor). This lemma is complemented by our key algorithmic correctness lemma, Lemma 4.4, which states that (under a few technical assumptions which hold essentially without loss of generality), we can produce such "weak estimates" from the sampled edges and vertices with high probability.

Future directions
Via the trivial reduction from Max-CUT, it is known that for all ǫ > 0, streaming algorithms There are a number of interesting alternatives for what could happen between ω( √ n) and o(n) space. Three main scenarios are: 2. "Lower bounds matching Theorem 1.3": Beating 0.483 requires Ω(n) space. 7 3. "Approximation vs. space tradeoff": Beating 0.483 can be achieved in o(n) space, but ( 1 2 −ǫ)approximations for ǫ > 0 require arbitrarily close to Ω(n) space for arbitrarily small ǫ.
We include a few brief remarks on these possibilities and speculate on why something like the third alternative may be plausible. Firstly, we mention that on the algorithmic side, in the classical setting Trevisan [Tre98] analyzed the natural linear programming (LP) relaxation for Max-DICUT, and showed that this LP achieves a 1 2 -approximation (though he mentions the result was already folklore); Halperin and Zwick [HZ01] showed further that one can always take the optimal solutions of the LP to be half-integral and used this to give an alternative "combinatorial" interpretation of the LP. 8 Is there some hope for collecting enough information in the streaming setting (even in, say, O(n 0.99 ) space) to simulate one of these algorithms?
Secondly, we recall that the original streaming inapproximability result for the related problem Max-CUT, due to [KKS15], used the hardness of a two-player one-way communication problem called Boolean-Hidden-Matching (introduced in [GKK + 08]). Very informally, in this game, Alice receives some information about each vertex, and Bob receives some edges and information about each edge which supposedly corresponds to Alice's knowledge of its endpoints. 9 How much information does Alice have to send to Bob for him to tell whether his per-edge information is correct? Ω( √ n) space is sufficient because of the so-called "birthday argument": Alice can send her information for Ω( √ n) vertices, at which point it becomes likely that Bob will see Ω(1) edges which Alice has informed him about. Thus, the simplest hardness proofs for CSPs break down at Ω( √ n) space, and this is for precisely the same reason the above algorithm for Max-DICUT works with O( √ n) space! The authors of [KKS15] also observed that a more general problem, called Boolean-Hidden-Hyper-Matching (introduced in [GKK + 08]), in which Bob instead receives tuniform hyperedges, gives (suboptimal) hardness for Max-CUT in o(n 1−1/t ) space. (This is because for Bob to see Ω(1) correctly labeled edges in the "birthday" protocol, Alice needs to send labels for each vertex with probability n −1/t .) This was subsequently extended in [KK19] to optimal hardness for Max-CUT even in o(n) space.
All this is to say that it is possible for there to be threshold at, for instance, o(n 2/3 ) space, where Max-DICUT's approximability changes. Indeed, there is a concrete reason to ask about this. Feige and Jozeph [FJ15] construct a pair of graphs, whose Max-DICUT values differ by a factor 0.4899, which cannot be distinguished by algorithms which only inspect edges and the biases of their endpoints. But, these graphs can easily be distinguished by algorithms which inspect paths of length 2 and the biases of their vertices. Seeing such paths, at least via the natural sampling procedure, requires storing Ω(n 2/3 ) vertices. 10 So can this information be used to improve on the algorithm in Theorem 1.3 given O(n 2/3 ) space? Conversely, can n-vertex "blowups" of the [FJ15] graphs be used to prove a 0.4899-inapproximability result in o(n 2/3 ) space -perhaps based on some communication problem such as Boolean-Hidden-Hyper-Matching?

Outline of the paper
In Section 2 we introduce some notation and review some background material. The main technical content of the paper is from Section 3 onwards, which can be divided into two independent steps. In the first step, we reduce approximating Max-DICUT (up to a factor 0.483) on a graph G to estimating a certain kind of "weak snapshot" of the graph G. In the second step, we show how such a "snapshot" can be measured using a streaming algorithm, and use this to design an approximation algorithm for Max-DICUT.
The first step begins in Section 3. Here, we formally define objects such as the "bias matrix" and "bias-degree array" of a graph which capture our informal notions of snapshots. Then, we give a self-contained statement of the type of estimate we are looking to find in the algorithm. This section culminates in a lemma (Lemma 3.22) which "reduces" the Max-DICUT approximation task to a weak estimation problem for the bias-degree array. We state also various smaller lemmas which together imply Lemma 3.22. We postpone the proofs of the lemmas until Section 6 and move onto the algorithm.
The second step takes place in Sections 4 and 5. Specifically, in Section 4, we design an algorithm for "weak estimate" which fulfills the premises of Lemma 3.22; we also include various "wrapper" algorithms using this to actually estimate the Max-DICUT value of a graph, culminating in a proof of Theorem 1.3 (in its technical form Lemma 4.2). In Section 5 we prove our central correctness lemma (Lemma 4.4), which states roughly that the estimate produced by the algorithm fulfills the premises of Lemma 3.22, by analyzing all the errors that arise in the algorithm from sampling, estimating the biases and degrees of vertices, etc.

Matrices and arrays
For ℓ ∈ N, we let M ℓ def = R ℓ×ℓ denote the space of real ℓ × ℓ matrices, M ℓ ≥0 ⊆ M ℓ the space of matrices with nonnegative entries, and M ℓ ∆ ⊆ M ℓ matrices with nonnegative entries summing to 1. For i, j ∈ [ℓ], M (i, j) denotes the (i, j)-th entry of M . Given two matrices M, N ∈ M ℓ , we let M − N 1 and M − N ∞ denote their entrywise 1-and ∞-norms, respectively, i.e., For k, ℓ ∈ N, we define analogues of this notation for four-dimensional arrays: ≥0 nonnegative arrays, and A k,ℓ ∆ nonnegative arrays summing to 1; we also define 1-and ∞-norms for arrays. We typically use the letters A and B for four-dimensional arrays, and M and N for (two-dimensional) matrices.

(Directed) graphs, degrees, biases, and (directed) cuts
In this paper, we consider graphs without self-loops. 11 We give two slightly different definitions of graphs, which we call unweighted and weighted graphs. The algorithm we present handles unweighted graphs, but the analysis requires the more general notion of a weighted graph. We take care in lemma statements to indicate which kind of graph we are considering.
An unweighted graph G is given by a set V (G) of vertices and a set E(G) ⊆ {(u, v) : u = v ∈ V (G)} of edges. We typically denote n = |V | and m = |E|.
A weighted graph on a vertex-set V = V (G) is defined by an adjacency matrix AdjMat G ∈ M V ×V ≥0 with zeros on the diagonal. An unweighted graph G can be viewed as a weighted graph defined by an adjacency matrix Given a vertex v ∈ V in a weighted graph G, we define its out-and in-degrees and its (total) degree and the overall Max-DICUT value of G as the maximum value of any cut:

Concentration
We write exp(x) = e −x . We shall need a number of concentration inequalities which operate in different parameter regimes of interest. We list several well-known inequalities as well as some convenient corollaries.

Sparsification for Max-DICUT
The following lemma is a standard statement about sparsification for the Max-DICUT problem, which essentially lets us reduce to considering graphs with linearly many edges. We include the proof in Appendix A for completeness. Lemma 2.9 (Linear sparsification preserves Max-DICUT values). There exists a universal constant C spar > 0 such that the following holds. For every ǫ spar ∈ (0, 1) and n, m ∈ N, suppose C spar n/(ǫ 2 spar m) ≤ p spar ≤ 1. Then for every unweighted graph G on n vertices with m edges, if we let G spar be the random (unweighted) graph resulting from throwing away every edge of G independently with probability 1 − p spar , then with probability 99/100 over the choice of G spar , we have |val G − val Gspar | ≤ ǫ spar and |m Gspar − p spar m| ≤ ǫ spar p spar m.

k-wise independent hash families
The following definition of a k-wise independent hash family will play a role in the algorithm we present in Section 4 below. 3 Reducing Max-DICUT approximation to "weak estimates" of the bias-degree array In this section, we develop some machinery to reduce the Max-DICUT approximation problem for a graph G to a certain kind of "weak estimation" problem for a kind of "snapshot" of G called its "bias-degree array". In Section 3.2 below we outline this reduction, but to begin, we formally define snapshots and state the result of [FJ15] upon which we will rely.

Intervals and thresholds
Let T ℓ ⊆ R ℓ+1 denote the space of vectors t = (t 0 , . . . , t ℓ ) such that t 0 < · · · < t ℓ . We call such a vector a threshold vector of length ℓ. Given a threshold vector t ∈ T ℓ , for any If along with a refinement t ′ ∈ T ℓ ′ of t ∈ T ℓ we are given some vector r = (r 1 , . . . , r ℓ ) ∈ R ℓ , we can define an inherited vector

Bias matrices
Let T ℓ ±1 ⊆ T ℓ denote the subset of threshold vectors with t 0 = −1 and t ℓ = 1. We think of such vectors as defining partitions of biases in graphs. For shorthand, given a weighted graph G and a (nonisolated for the index representing the "bias class" containing v, and given a pair of nonisolated vertices u, v, we write b-ind t G (u, v) def = (ind t (bias G (u)), ind t (bias G (v))) ∈ [ℓ] 2 for their pair of bias classes. Definition 3.2 (Bias matrix [SSSV23]). Given a weighted graph G and threshold vector t ∈ T ℓ ±1 , we define the bias matrix BiasMat G,t ∈ M ℓ ∆ by In other words, the matrix BiasMat G,t counts the fraction of edges in the graph between each pair of bias classes. Note that this is a normalized matrix, i.e., its entries sum to 1, unlike the adjacency matrix AdjMat G . This is simply a matter of convenience.
The importance of the bias matrix is that it can be used to estimate the Max-DICUT value of a graph: Lemma 3.3 (Feige and Jozeph [FJ15]). There exists a constant α FJ ∈ (0.483, 0.4899), ℓ FJ ∈ N, a vector of bias thresholds t FJ ∈ T ℓ FJ ±1 , and a vector of probabilities r FJ = (r 1 , . . . , r ℓ ) ∈ [0, 1] ℓ FJ such that the following holds.
For every weighted graph G, Though we will not need this fact, we remark that the estimate for val G given in the lemma corresponds to a simple randomized assignment for G, namely the so-called "oblivious" assignment which assigns each nonisolated vertex v ∈ V (G) to 1 with probability r i and 0 otherwise, where is its bias class. We will rely on a "robust" version of the [FJ15] result which allows using an "estimate" for the bias matrix BiasMat G,t (in exchange for some loss in the approximation factor), and also allows using a "refinement" of the [FJ15] partition (as opposed to the partition itself). This takes the form of the following corollary, which is an analogue of [SSSV23, Corollary 3.5] except with 1-norm instead of ∞-norm errors. For completeness, we give a proof in Section 6.3. Corollary 3.4 ("Robust [FJ15] with refinement"). Let α FJ , ℓ FJ , t FJ , r FJ be as in Lemma 3.3. Let ℓ ∈ N, let t ∈ T ℓ be a refinement of t FJ , and let r ∈ [0, 1] ℓ be the vector inherited from r FJ .
Let G be a weighted graph on n vertices, and let M ∈ M ℓ be an estimate for G's bias matrix:

The bias-degree array
Next, we introduce a new and more refined version of a snapshot of a graph G which also takes into account the degrees of the vertices. Suppose we also have a threshold vector d ∈ T k partitions vertex degrees in G, in the following sense: all nonisolated vertices in G have degree between d 0 and d k . We define similar notations: This lets us define: Definition 3.6 (Bias-degree array). Given a weighted graph G and threshold vectors t ∈ T ℓ ±1 , This array is only more informative than the bias matrix because the bias-matrix can be recovered via "projections". More precisely: Definition 3.8 (Projecting arrays into matrices). Given an array A ∈ A k,ℓ , we define a matrix Proj(A) ∈ M ℓ by projecting onto the third and fourth coordinates, i.e.,

Outline
The algorithm of Feige and Jozeph [FJ15] (in the form of Corollary 3.4 above) reduces the task of estimating the Max-DICUT value of a graph G to estimating its bias matrix BiasMat G,t in 1norm. Now, our goal is to further reduce this task to a notion which we call weakly estimating the smoothing of the bias array BiasDegArr G,d,t .
The motivation for this reduction is that the final "weak estimation" task can be carried out directly in the streaming setting using an "edge-and-vertex-subsampling" strategy (as described in Section 1.5). We carry this out in the following two sections, which contain an explicit description of the algorithm (Section 4) and its analysis (Section 5). For now, we introduce some more definitions and lemmas and build towards a statement of a lemma, Lemma 3.22, which precisely states that this notion of "weak estimation" is sufficient. Proofs of this and several preliminary lemmas which we state in this section are postponed until Section 6 below.
The reduction from approximating the Max-DICUT value of a graph G proceeds as follows: 1. We reduce to estimating a "smoothed" version of BiasMat G,t in 1-norm (see Lemma 3.13 below); each entry in the smoothed matrix is a (weighted) average over a "window" of surrounding entries in the original matrix.
2. We reduce this to estimating smoothed version of the array BiasDegArr G,d,t in 1-norm (see Proposition 3.16 below).
3. Finally, we reduce this to a certain notion of a "weak estimate", which roughly corresponds to allowing certain small mistakes in the estimate, in terms of which entries are counted and with what weights (see Corollary 3.21 below).
More concretely, we make the following definitions: We state various basic but useful facts about windows in Section 6.1 below.

Reducing approximating Max-DICUT value to estimating a "smoothed" bias matrix
We now define what it means to smooth a matrix M ∈ M ℓ over windows of size w.
Let G be a weighted graph and M = BiasMat G,t be its bias matrix. Then there exists a weighted graph H such that |val G − val H | ≤ C smooth ǫ bias (w + 1) and the bias matrix N = BiasMat H,t satisfies N − M ∼w 1 ≤ C smooth ǫ bias (w + 1).
The proof of Lemma 3.13 is given in Section 6.5 below, and is somewhat involved: we essentially make many copies of each vertex in G, and then "perturb" the bias of each copy by tweaking the weights of incident edges, in order to make the final bias matrix resemble M ∼w . Lemma 3.13 is useful because it implies both that (1) the " [FJ15] estimate" will be similar between H's actual bias matrix N and G's smoothed bias matrix M ∼w , and that (2) the Max-DICUT values of G and H are similar. Since we also know (3) that the " [FJ15] estimate" for H approximates H's Max-DICUT value (by Corollary 3.4), these three facts together will imply that the " [FJ15] estimate" based on M ∼w approximates G's Max-DICUT value.

Reducing estimating the bias matrix to estimating the bias-degree array
Unfortunately, we will not be able to directly estimate entries of the smoothed bias matrix BiasMat ∼w G,t using our sampling-based algorithm. Roughly, this is because there may be huge discrepancy between degrees of vertices (indeed, from O(1) to Ω(n)), and the subsampling parameters will depend on the degree. So, we reduce to the problem of estimating more refined quantities: smoothed versions of the array BiasDegArr G,d,t . Our hope is that, if the degree partition is fine enough, these quantities can actually be estimated.
We have also have an analogue of Proposition 3.12 (proof omitted for syntactic similarity): The following definition and proposition roughly state that to estimate the matrix BiasMat ∼w G,t in 1-norm, it suffices to instead estimate the array BiasDegArr ∼w G,d,t in 1-norm. Together with Fact 3.9, this proposition does give the desired reduction from the problem of 1norm estimation for BiasMat ∼w G,t to 1-norm estimation for BiasDegArr ∼w G,d,t . We prove the proposition (again by double-counting) in Section 6.2 below.
3.6 A notion of "weakly estimating" the bias-degree array ≥0 be an array with nonnegative entries. For the final step in our reduction, we define a certain notion of a "weak estimate" for the smoothed array A ∼w , and give a statement (Corollary 3.21 below) which roughly says that such a "weak" estimate suffices for a 1-norm estimate (with some loss in parameters). Such a "weak" estimate will be what we actually aim to achieve in the algorithm, with A = BiasDegArr G,d,t .
The notion of "weak estimate" relies on the definition of two additional arrays A −w , A +w ∈ A k,ℓ ≥0 which satisfy the inequality A −w ≤ A ∼w ≤ A +w entrywise and account for "off-by-one" errors when estimating A ∼w . We first describe these arrays informally as the actual definitions may appear quite technical. Consider an "estimation" function ξ : for the graph G, which takes as input the index (a, b, i, j) of an entry in the array A, and outputs a tuple ξ(a, b, i, j) which is promised to differ from (a, b, i, j) by at most 1 in each entry. (This will correspond to issues with "borderline" vertices when A = BiasDegArr G,d,t , as described in Section 1.5 above.) Now suppose we tried to estimate the entry A ∼w (a, b, i, j) using the expression The quantities A −w (a, b, i, j) and A +w (a, b, i, j) are lower-and upper-bounds for this expression, respectively, based on the "worst possible" function ξ.
To be more precise, we define the arrays A −w , A +w ∈ A k,ℓ ≥0 as follows: Definition 3.17 (Upper-and lower-bound normalization factors). Let w < k, ℓ ∈ N. Then for Definition 3.18 (Upper-and lower-bound arrays). Let w < k, ℓ ∈ N and A ∈ A k,ℓ . We define two arrays A −w , A +w ∈ A k,ℓ ≥0 by defining, for all a, b ∈ [k] and i, j ∈ [ℓ]: Hence, (since A has nonnegative entries) we have a, b, i, j), since they sum over windows around (a, b, i, j) of sizes w − 1, w, and w + 1, respectively, using increasing normalization factors. We also have the following simple lemma: Proof. For the first inequality, see above. For the second, note from Definitions 3.14 and 3.17 that A second key lemma, which we prove in Section 6.4 below, is that we can control the error between these arrays: Lemma 3.20 ("Sandwiching A ∼w "). There exists a universal constant C win > 0 such that for every w < k, ℓ ∈ N and every A ∈ A k,ℓ ∆ , A +w − A −w 1 ≤ C win /w.
Immediately we get the following corollary, which states that a "sandwiched entrywise" estimate for A ∼w is also an estimate in 1-norm. Note that there is a substantial loss in parameters, corresponding to moving from ∞to 1-norm.
Let G be a weighted graph such that for every vertex v ∈ V (G), either deg G (v) = 0, or d 0 ≤ deg G (v) ≤ d k . Let A = BiasDegArr G,d,t , and suppose A ∈ A k,ℓ is a "weak estimate" for A ∼w , in the sense that A −w − ǫ err ≤ A ≤ A +w + ǫ err entrywise. Then for M = Proj( A), In the next section, we present an algorithm which uses the reduction in Lemma 3.22 to approximate the Max-DICUT value of an unweighted graph G, up to a fixed constant approximation error ǫ. We briefly remark on the parameters with which Lemma 3.22 will be invoked. Since ǫ will a fixed constant, we will need to set w = O(1/ǫ) (in order for δ err to be sufficiently small). Thus, we will need ǫ bias = O(ǫ 2 ) (to make δ bias sufficiently small), forcing ℓ = O(1/ǫ 2 ) (see Fact 3.1). Moreover, in order to get estimates in sufficiently small space, we will need a relatively fine degree partition d i /d i−1 = O(1) (we will use d i /d i−1 = 2 for simplicity), forcing k = Θ(log n). This means we will need to set ǫ err = O(ǫ 5 / log 2 n) in order for δ err to be sufficiently small.

The algorithm
In this section, we present an algorithm that approximates the Max-DICUT value of an arbitrary unweighted graph, thereby proving Theorem 1.3 (see Lemma 4.2 below). The algorithm itself has to deal with a number of technical issues, so we begin by outlining the algorithm and giving a number of pointers which hopefully make it easier to digest.

Overview
Informal recap. The main concrete goal of the algorithm is to produce a "weak estimate" for the bias-degree array BiasDegArr G,d,t of a graph G, in the sense of the hypotheses of Lemma 3.22 from the previous section. We quickly review the motivations behind this task from the discussion in Section 1.5.
At the highest level, we want to sample random edges in a graph G and estimate the biases of their endpoints, in order to estimate the bias matrix BiasMat G,t ; this is sufficient to approximate the Max-DICUT value of G using the algorithm of Feige and Jozeph [FJ15] (see Lemma 3.3). We aim to design a "sampling procedure" in which we sample several different sets S 1 , . . . , S k of vertices whose degree is "roughly" d i for some partition d 0 ≤ · · · ≤ d k of degrees in G; we also store (sparse versions of) the neighborhoods of these vertices. Then, we aim to use the edges which showed up in these neighborhoods to estimate entries of the bias-degree array BiasDegArr G,d,t . (However, we still have to deal with a number of errors corresponding to mis-estimating parameters of sampled edges, in particular the biases and degrees of their endpoints, and thus we can only get a "weak estimate".) Outline of the algorithm. Via Lemma 3.22, we seek to estimate the entries of the smoothed bias-degree array A ∼w where A = BiasDegArr G,d,t . Roughly, this measures how many edges e = (u, v) are there in G such that (ind d (deg G (u)), ind d (deg G (v)), ind d (bias G (u)), ind d (bias G (v)) ∈ Win w,k,ℓ (a, b, i, j); that is, in G, u's degree, v's degree, u's bias, and v's bias are within w intervals of a, b, i, j, respectively, with respect to some global partition d of degrees and t of biases. (Actually, we are summing normalization factors ν ∼w,ℓ,k over these edges, but this technical detail can be ignored for now.) To do this, for each "layer" a ∈ {1, . . . , k}, we fix some probabilities q a , p a ∈ [0, 1]. We subsample the edges of G with probability q a and then subsample positive-degree vertices in G a with probability p a to get a subset of vertices, which we denoted vStored a in the algorithm. We hope to store the G a -neighborhoods of these vertices to get a subset of edges denoted eStored a . Ideally, we can use eStored a to estimate the degrees and biases of vertices in vStored a , and further, if we see an edge stored in eStored a between vertices in vStored a and vStored b , we can count it in the appropriate entry of the bias-degree array. However, note that eStored a cannot necessarily store all neighbors for every vertex in vStored a ; in particular, while our edge subsampling ensures that vStored a is unlikely to contain vertices of G-degree much less than d a , it may still contain vertices of G-degree much greater than d a , in which case we can not hope to store all its neighbors.
Some pointers. It is very helpful to remember that there are two distinct sources of randomness in the algorithm: We "sparsify" the graph by subsampling edges, and then subsample which vertices we actually store. In the analysis we will first analyze this edge-subsampling, and then conditioned on certain "good outcomes" for the edge-subsampling we will analyze the vertex-subsampling. Correspondingly, it is useful to keep in mind the graph G a consisting of all the edges sampled in layer a (each is sampled w.p. q a ) and the set N a of positive-degree vertices in G a . (However, the actual streaming algorithm is not necessarily be able to store these sets as they can grow too large; it only stores subsets eStored a and vStored a , respectively.) When we actually see an edge e = (u, v) in G a , how do we know what to do with it (i.e., which entry of the matrix should it contribute to)? Note that E [deg Ga (v)] = q a deg G (v). Thus, we can hope to use q −1 a deg Ga (v) (which we call v's "apparent degree") as an estimate for deg G (v). Roughly, this should work out if deg G (v) is decently large; for instance, we can use the Chernoff bound to show that w.h.p.
, so the apparent degree moves by at most 1 interval relative to the actual degree. The same sort of analysis is necessary to analyze the bias of a vertex and ultimately prove that we get a so-called "weak estimate". This is asserted in Lemma 4.4 below.
Finally, we remark that the subsampling probabilities q a and p a decrease and increase, respectively, as a function of a. Indeed, for "typical" a, p a will be inversely proportional to q a , i.e., p a q a will have a fixed value independent of a. However, since q a and p a are probabilities and are in particular at most 1, when a is small we will have to take q a = 1 while when a is large we will take p a = 1. That this is necessary is unsurprising if we consider "extremal" graphs, e.g. low-degree regular graphs (where we cannot hope to subsample edges without losing information) and graphs consisting of high-degree stars (where we cannot hope to subsample high-degree vertices without losing information). 13 Some technicalities. We describe several more technical issues that occur in the algorithm, with an aim towards increasing readability. We encourage the reader to ignore all these details in the first pass over the algorithm and its analysis.
Firstly, we can essentially reduce to the case where the number of edges in G satisfies √ n ≤ m ≤ O(n); if m is smaller, we can simply store all edges in the graph using O( √ n) space, and if m is larger, we can globally sparsify while preserving the Max-DICUT value up to some small loss (see Lemma 2.9 above). Thus, our main subroutine (DiCutEstimator below) will operate under this kind of assumption, though we relax it in the final algorithm (WrappedDiCutEstimator below) for completeness. Also, recall that a streaming algorithm in general is not given the number of edges in the stream as input. To solve this issue, as in [SSSV23], we rewrite the code of DiCutEstimator to use a value m as an "estimate" for m when setting all parameters. The hope is that when m roughly equals m (say, up to a factor of 2) the algorithm will still be correct; in particular, we will run the algorithm for several values of m in parallel. If m is too small we may end up storing too many edges for the space bound, while if m is too large we may store too few edges for correctness. The latter is acceptable because after the stream finishes we do know the correct number of edges m and therefore can discard results for incorrect m. But to deal with the other case, we need to ensure that DiCutEstimator never uses too much space even if m is much too small. Thus, we add a condition called "overflow" which is triggered when the set eStored grows too large (though we eventually have to show that this condition would not be triggered when m is correct, see Lemma 5.3 below).
Finally, one remaining technical issue stems from the fact that when we want to subsample a set of nonisolated vertices in the subsampled graph G a , but we do not know the nonisolated vertices ahead of time. In particular, each time we see a new nonisolated vertex we want to toss a p-biased coin -but if we decide not to store a vertex, we need to "remember" this decision if we happen to see it again. This would be manageable if the algorithm had random access to the results of n biased coin flips, but this model would be somewhat nonstandard. Instead, as in [SSSV23], we observe that when proving concentration it is sufficient to have four-wise independence in the vertex-subsampling procedure, and thus, we decide whether to store a vertex by plugging it into a previously sampled four-wise independent hash function (see Lemma 2.11).

Describing the algorithm
The goal of this section is to prove Theorem 1.3. We begin by presenting an algorithm, called DiCutEstimator, for estimating the Max-DICUT value of a stream of edges corresponding to a graph G under certain "niceness" conditions regarding the number of edges in G. Specifically, the algorithm DiCutEstimator depends on an "estimate" m for the number of edges m in G; for correctness, we require that m is within a factor of roughly two of m, and for the space bound, we require that m is Ω( √ n) and O(n), where n is the number of vertices in G. Reducing to this case is fairly standard -essentially a combination of guessing the correct m and using sparsification -but for completeness we also present a full algorithm, called WrappedDiCutEstimator, which approximates the Max-DICUT value for arbitrary graphs. Theorem 1.3 follows immediately from the correctness and efficiency of this algorithm, which we state in Lemma 4.2. However, the correctness of DiCutEstimator, and by extension WrappedDiCutEstimator, will depend on a key correctness lemma (Lemma 4.4 below) whose proof is postponed until Section 5.
DiCutEstimator itself depends on two subroutines, called LayeredSampler and BiasDegArrEstimator, which we present next. The former is responsible for subsampling edges and vertices, and is the only subroutine that needs the stream σ, while the latter is responsible for using the sampled information to estimate the bias-degree array. We also remark that LayeredSampler is the "space hog" of the algorithm: the final space usage will be determined by the number of edges and vertices stored by LayeredSampler, since the remaining code essentially just does arithmetic. 14 We also include several tables containing definitions of parameters to be used in the algorithms.

Notation
Value Description ǫ ′ > 0 ǫ/(8(2 + C win + 2C smooth )) where C win and C smooth are as in Lemmas 3.13 and 3.20 Scaled-down error (for use in triangle inequalities) w ∈ N 1/ǫ ′ Size of windows for smoothing ǫ bias > 0 ǫ ′ /(w + 1) Maximum width of intervals in the refinement t of t FJ (see next line) t ∈ T ℓ Refinement of t FJ into ℓ intervals of width at most ǫ bias 14 Actually, this is true for DiCutEstimator, but in WrappedDiCutEstimator there is an additional log factor from running O(log n) copies of DiCutEstimator in parallel.

Notation Value
Description m min ∈ N √ n Minimum number of edges handled in DiCutEstimator m max ∈ N C spar n/(ǫ ′ ) 2 where C spar is as in Lemma 2.9 Maximum number of edges handled in DiCutEstimator (see Lemma 2.9) k * ∈ N 6 log log n Number of degree intervals before we begin subsampling edges D ∈ N 2 k * +w+2 W.h.p. bound on max-degree of "counted vertices" in subsampled graphs (parameter for space bound), note that D = O ǫ (log 6 n) eCutoff log 7 n Maximum number of stored neighbors per vertex Maximum number of stored vertices per layer, note that vCutoff = O ǫ ( √ n log 6 n) (assuming m ≤ m max ) Table 3: Global parameters determined by ǫ, n, and m.

Algorithm 1 DiCutEstimator(σ; ǫ, n, m)
Goal: Estimate the Max-DICUT value in a graph stream, given an estimate for the number of edges 1: Import parameters defined in Table 1.
When the size of the graph is "nice" and correctly estimated by m, we claim that DiCutEstimator uses small space and (with high probability) outputs a good estimate of val G : , then with probability at least 9/10, the We will prove Lemma 4.1 in Section 4.3 below (modulo the proof of another lemma). Next, we present the "wrapper" algorithm which reduces the case of general input graphs to the case handled by DiCutEstimator (i.e., ensures the conditions in Lemma 4.1).

17: end for
The desired properties of WrappedDiCutEstimator are asserted in the following lemma: Lemma 4.2 (Correctness and efficiency for WrappedDiCutEstimator). Let ǫ > 0, n ∈ N, and G be an unweighted graph on n vertices. Let σ be a stream consisting of edges of G in arbitrary order. Then running WrappedDiCutEstimator on the stream σ uses Moreover, with probability at least 9/10, its output v satisfies We also prove Lemma 4.2 in Section 4.3 below, which completes the proof of our main theorem. Now, we delve into the "meat" of the algorithm, beginning with the sampling algorithm LayeredSampler, which, roughly speaking, subsamples vertices and edges for us to store.

Algorithm 3 LayeredSampler(σ; ǫ, n, m)
Goal: Output a "representative sample" of vertices with various degrees and their neighborhoods 18: Import parameters defined in Tables 1 to 4 Toss a biased coin which is 1 with probability q a , and let z denote its output.
As mentioned above, the space usage of LayeredSampler essentially determines the space usage of the entire algorithm, and this space usage is small because of the bound on the number of stored vertices and edges in Lines 27 and 28. Finally, here is the algorithm BiasDegArrEstimator which uses the output of LayeredSampler to estimate the (smoothed) bias-degree array.
The proof of this lemma is more involved, and is postponed until Section 5. Assuming To prove correctness, we can now assume m/2 ≤ m ≤ 2m. We apply Lemma 4.4 to conclude that the output A of BiasDegArrEstimator lies between A −w and A +w entrywise up to additive error ǫ err = ǫ ′ /(kℓ) 2 where A = BiasDegArr G,d,t . Then, we can apply Lemma 3.22, and we conclude that for M = Proj( A), we have: Since all other values of m are ignored by Line 16, it suffices to consider only this value of m and show that we output a correct estimate. To do so, we use Lemmas 4.1 and 2.9. In particular, let G spar denote the graph corresponding to σ spar , so that G spar is formed from G by sampling each edge independently w.p. p spar . Let m spar = m Gspar . We claim that with probability 999/100 over the choice of G spar , |val G − val Gspar | ≤ ǫ ′ (4.6) and |m spar − p spar m| ≤ ǫ ′ p spar m. (4.7) Indeed, if p spar = 1 then G spar = G so the statement holds trivially. Otherwise, p spar = m max / m so that m spar = m max . Now we can apply Lemma 2.9 with ǫ spar = ǫ ′ , since using the definition of m max and the assumption m ≥ m (Eq. (4.5)). Finally, we condition on G spar such that Eqs. (4.6) and (4.7) occur, and we want to apply Lemma 4.1 to G spar . To do this, we have to check that Thus, by Lemma 4.1, the output v of DiCutEstimator on G spar satisfies (α FJ − 8ǫ ′ (1 + C win + 2C smooth ))val Gspar ≤ v ≤ val Gspar . We can add this inequality with Eq. (4.6) to conclude that as desired.

Correctness of BiasDegArrEstimator: Proving Lemma 4.4
The goal of this section is to prove Lemma 4.4, which says that the estimated array A lies between the arrays BiasDegArr −w G,d,t and BiasDegArr +w G,d,t , up to some additive error. Throughout this section, we work with a fixed ǫ, n, m, σ which also fixes G and m. Besides the variables in Tables 1 to 4, we also define the following notation: For a ∈ [k], G a will denote the random variable denoting the subgraph of G containing all the edges for which z = 1 in Line 23 in the a-th execution of the loop. We will use m a to denote the random variable equal to the number of edges in G a and N a to denote the set-valued random variable that is equal to the set of all non-isolated vertices in G a . Note that these random variables are all determined by the randomness in Line 23.
For a ∈ [k], we also define the set-valued random variable S a = {v ∈ [n] : π a (v) = 1}, that is, S a is the set of all vertices that hash to 1 under π a . Note that S a is determined by the randomness in Line 19. Also, note that the randomness' in Lines 19 and 23 are independent.
The plan of attack is to build up to the full proof by defining several "good" events, that each happen with high probability and together imply that we get the desired output. We start by analyzing the condition in which our algorithm returns overflow in Section 5.1. In Sections 5.2 and 5.3, we analyze the degrees and the biases (respectively) of the vertices the G a and show that they are close to the corresponding values in G. By Lemma 5.16, this implies that our estimates νEst in Line 36 are in the desired range. Finally, in Sections 5.4 to 5.6, we build on these lemmas and show that our final output is as desired.

Overflow condition in Algorithm 3
The goal of this section is to define and analyze two events E of1 and E of2 such that Algorithm 3 never returns overflow when they occur. These are defined in Lemma 5.1 and Lemma 5.2 respectively.
Lemma 5.1. We have Pr(E of1 ) ≥ 999/1000, where the probability is over the randomness in Line 23 and E of1 is defined as follows: For every a ∈ [k], we have: Proof. Note that for all a ∈ [k], the random variable m a is the sum of m independent and identically distributed indicator random variables that take the value 1 with probability q a . For all a ∈ [k] such that p 0 ≤ q a , this fact together with Lemma 2.1 gives: Similarly, for all a ∈ [k] such that p 0 > q a which implies 5ρ √ m ≥ 3p 0 m ≥ 3q a m, Corollary 2.4 gives: The lemma now follows by combining the two inequalities above and applying a union bound over all a ∈ [k].
Next, let G 1 , . . . , G k be a set of subgraphs of G that may be sampled in Line 23. For convenience, we shall often abbreviate G [k] = G 1 , . . . , G k . Observe that G [k] determines whether or not E of1 occurs. We have: Thus, assume that p 0 ≤ q a . As E of1 occurs, we have |N a | ≤ 2m a ≤ 4q a m by Lemma 5.1. For all v ∈ N a , define the indicator random variable I v to be 1 if and only if v ∈ S a . Note that these random variables are pairwise independent as Line 19 samples a 4-wise independent hash function. Define I = v∈Na I v and note that (as I is a sum of pairwise independent indicator random variables) Var[I] ≤ E [I] ≤ 4p a q a m = 4p 0 m as p 0 ≤ q a . We get: We now formalize our claim above that Algorithm 3 never returns overflow if E of1 and E of2 occur.
Lemma 5.3. Fix any G [k] such that E of1 occurs. If G [k] is sampled in Line 23 and E of2 occurs, then the following hold (with probability 1):

Algorithm 3 does not return overflow.
2. For all a ∈ [k], we have vStored a = N a ∩ S a .

For all
Proof. We fix the randomness in Lines 19 and 23 arbitrarily such that both G [k] and E of2 occur and show that Items 1 to 4 hold. Note that fixing the randomness fixes the value of all variables in Algorithms 3 and 4. We show each part in turn.
1. Note that Algorithm 3 returns overflow only if there exists a ∈ [k] such that at least vCutoff non-isolated vertices v in G a satisfy v ∈ S a , or equivalently, if |N a ∩ S a | ≥ vCutoff. By Lemma 5.2, this can never happen if E of2 occurs.
3. As the =⇒ direction is trivial, we only show the ⇐= direction. We only show the first equivalence as the proof for the second one is analogous. Let v ∈ [n] be arbitrary such that (u, v) ∈ G a . Due to Item 1, we are guaranteed that the algorithm executes Line 28 with e = (u, v) and a and v ′ = u. The "if" in Line 28 is satisfied due to Line 26 and the fact that u ∈ vStored a and we get (u, v) ∈ eStored a , as desired.

Degrees after edge-subsampling
For a ∈ [k] and v ∈ [n], define a random variable for the apparent degree index as follows: In the above definition, we adopt the convention that the right-hand side is −∞ if deg Ga (v) = 0. We remark that this definition is similar to but different from the quantity dEst a (v) we defined in Algorithm 4, since that was only defined for vertices in vStored a and counted only the edges in eStored a . We begin with the following lemma, which gives a general characterization of degrees of vertices in the graphs G a .
Lemma 5.5. We have Pr E deg ≥ 999/1000, where the probability is over the randomness in Line 23 and E deg is defined as follows: For all a ∈ [k] and v ∈ [n], we have: Proof. We will upper bound the probability that E deg does not happen. For this, we fix a ∈ [k] and v ∈ [n] and upper bound the probability that one of Items 2 and 3 does not hold for this a and v by o(1/n 2 ). The proof then follows by a union bound. If a ≤ k * , then deg Ga (v) = deg G (v) and q a = 1 and there is nothing to show. We therefore assume that a > k * =⇒ q a = 2 k * −a . Note that deg Ga (v) is a sum of deg G (v)-many independent and identically distributed indicator random variables, each of which is 1 with probability q a . Consider first the case deg G (v) ≥ 2 a−w−3 . This means that q a deg G (v) ≥ 2 k * −w−3 ≥ 50 log n. In this case, we use Lemmas 2.1 and 2.2 to get: In this case, we use Corollary 2.4 to get: Adding the three bounds gives the result.
We can deduce several nice properties about the random variable d-ind d a (v) defined in Eq. (5.4) when E deg happens.
Lemma 5.6. If E deg occurs, the following hold for all a ∈ [k] and v ∈ [n] (with probability 1): . Proof. Fix any G [k] such that E deg occurs. Also, fix a and v. Fixing G [k] also fixes the value of deg Ga (v) and d-ind d a (v). We prove each part in turn: 1. If not, we have from Item 2 of Lemma 5.5 that deg G (v) > 2 a−w−3 . Item 1 of Lemma 5.5 then implies the following contradiction: there is nothing to show. Otherwise, we have from Item 2 of Lemma 5.5 that deg G (v) > 2 a−w−3 . Now, using Item 1 of Lemma 5.5, we get q −1 Next, for a ∈ [k], we define the following set valued random variable that is determined by the randomness in Line 23.
We also define the following sets: (5.8) Recall that we defined the parameter D = 2 k * +w+2 . These definitions satisfy: Lemma 5.9. If E deg occurs, the following hold for all a ∈ [k] (with probability 1):

For all
Proof. Fix any G [k] such that E deg occurs. Fixing G [k] also fixes the value of deg Ga (v) and d-ind d a (v) for all a ∈ [k] and v ∈ [n]. Fix a ∈ [k] as in the lemma. We prove each part in turn.
Let v ∈ V − a be arbitrary. By Eq. (5.8), we have d-ind d G (v) ∈ Win w−1,k (a). Using Items 1 to 3 of Lemma 5.6, we get deg It follows from Eq. (5.7) that v ∈ V a . As v ∈ V − a was arbitrary, we have V − a ⊆ V a , as desired. We now show that V a ⊆ V + a in the contrapositive. Let v ∈ [n]\V + a be arbitrary. By Eq. (5.8), Using Item 3 of Lemma 5.6 in the former case and Item 2 in the latter, we get that either In either case, we have from Eq. (5.7) that v ∈ [n] \ V a . As v ∈ [n] \ V + a was arbitrary, the result follows.

As
. As Item 1 of Lemma 5.5 implies that q −1 a deg Ga (v) < 2deg G (v) ≤ 2d k , we can continue as q −1 a deg Ga (v) ≤ 2 a ′ +w+3 . This means: . The result follows from Items 2 and 3 of Lemma 5.6.

Biases after edge-subsampling
For a ∈ [k] and v ∈ [n], we define a random variable for the apparent bias index as follows: (5.10) (The right hand side is undefined if deg Ga (v) = 0.) Note that this random variable is determined by G a and therefore, by the randomness in Line 23.
Lemma 5.11. We have Pr(E bias ) ≥ 999/1000, where the probability is over the randomness in Line 23 and E bias is defined as follows: For all a ∈ [k] and v ∈ V + a , we have: Proof. We will upper bound the probability that E bias does not happen. For this, we fix a ∈ [k] and v ∈ V + a and upper bound the probability that one of Items 1 to 3 does not hold for this a and v by o(1/n 2 ). The proof then follows by a union bound. If a ≤ k * , then G a = G and q a = 1 and there is nothing to show. We therefore assume that a > k * =⇒ q a = 2 k * −a and show Item 2 as the proofs of Items 1 and 3 is analogous. Note that deg-out Ga (v) is a sum of deg-out G (v)-many independent and identically distributed indicator random variables, each of which is 1 with probability q a . Thus, we have from Corollary 2.3 that: Proof. Fix any G [k] such that E bias occurs. Also, fix a and v. Fixing G [k] also fixes the value of b-ind t G (v) and b-ind t a (v). We assume that deg-out G (v) ≥ deg G (v)/2 as the proof for the case deg-in G (v) ≥ deg G (v)/2 is analogous. By Items 1 and 2 of Lemma 5.11, we have: It follows that As bias = 2deg-out/deg − 1, we get: As consecutive entries of t are at least ǫ bias /2 apart, this means that Next, for a ∈ [k] and i ∈ [ℓ], we define the following set valued random variable that is determined by the randomness in Line 23.
We also define the following sets for all a ∈ [k] and i ∈ [ℓ]: (5.14) These definitions satisfy: Proof. Follows immediately from Item 1 of Lemma 5.9, Lemma 5.12, and the definition of Win.
Recall the set vEst a,i defined in Line 35 and the sets N a and S a defined at the beginning of Section 5. We have: . For all u ∈ vEst a,i and v ∈ vEst b,j , it holds that: Proof. We fix the randomness in Lines 19 and 23 arbitrarily such that all the events in the lemma occur. Note that fixing the randomness fixes the value of all variables in Algorithms 3 and 4 and also fixes the random variables defined above. We prove each part in turn.
To continue, note that for any v ∈ vStored a such that deg eStoreda (v) < eCutoff, we have from Item 3 of Lemma 5.3 that deg-in eStoreda (v) = deg-in Ga (v) and deg-out eStoreda (v) = deg-out Ga (v). Conclude from Line 34 and Eqs. (5.4) and (5.10) that for any such v, we have d-ind d a (v) = ind d (dEst a (v)) and b-ind t a (v) = ind t (bEst a (v)). We can now continue as: 2. As u ∈ vEst a,i , we have by Line 35 that u ∈ vStored a and deg eStoreda (u) < eCutoff. From Item 3 of Lemma 5.3, this means that deg-in eStoreda (u) = deg-in Ga (u) and deg-out eStoreda (u) = deg-out Ga (u). Using Line 34 and Eqs. (5.4) and (5.10), this means that d-ind d a (u) = ind d (dEst a (u)) and b-ind t a (u) = ind t (bEst a (u)). As similar arguments apply for v, we get from Line 36 that: Now, as we have Definition 3.17, it suffices to show that: From Definition 3.10 and Eq. (3.5), this follows if we show that: This first inequality is due to Items 2 and 3 of Lemma 5.6 while the second inequality is due to Lemma 5.12 (note that Item 1 implies that u ∈ V a,i and v ∈ V b,j and we have Lemma 5.15).

Counting target edges after edge-subsampling
For a, b ∈ [k] and i, j ∈ [ℓ], define: Recall from the statement of Lemma 4.4 the notation A = BiasDegArr G,d,t . Next, for a, b ∈ [k] and i, j ∈ [ℓ], we define the random variables: (5.18) Recall the notation in Definition 3.18. The following lemma calculates the expectation of these random variables.
Lemma 5.19. For all a, b ∈ [k] and i, j ∈ [ℓ], it holds that: Proof. We only show the first equation as the proof of the second one is analogous. Note from Eq. (5.18) and linearity of expectation that it suffices to show that: This is because: Now, by Eq. (5.17), it suffices to show that, for all (u, v) ∈ G, we have: This is because: (Eqs. (5.8) and (5.14)) Using standard concentration bounds, we get: Proof. We will upper bound the probability that E count1 does not happen. For this, we fix a, b ∈ [k] and i, j ∈ [ℓ] and upper bound the probability that the first inequality does not hold for this a, b and i, j by o(1/n). The proof for the second inequality is similar and the lemma, thus follows by a union bound. Fix a, b ∈ [k] and i, j ∈ [ℓ]. We have from Lemma 5.19 and Corollary 2.6 that: where, for the last step, recall that k = log(2 m) = O ǫ (log n), while q k m = 2 k * −k m = m · log 6 n 2 m ≥ 0.5 log 6 n. So the negated expression in the exponent is Θ ǫ (log 2 n) and we get the required bound of o(1/n).

Counting target edges after vertex-subsampling
we can assume p a < 1 which means that p a = p 0 q −1 a . For convenience, define F = E − a,b,i,j ∩ G a and ∇ = ǫ ′ 2(kℓ) 2 · p a p b q a m. For (u, v) ∈ F , define the random variable: Plugging into Eq. (5.22), we get that X ) . Next, we claim that for all (u, v) ∈ F , there are at most 5D · p b p 0 many (u ′ , v ′ ) ∈ F such that I (u,v) and I (u ′ ,v ′ ) are not independent, where D and p 0 are as in Tables 2 and 3. Assuming this claim for now, Corollary 2.8 says: Observe that Lemma 4.4 is the same as showing Pr E good ≥ 99/100. We show this by upper bounding the probability of the complement event. Using a union bound, we have: (Lemmas 5.1, 5.5, 5.11 and 5.21) Thus, it suffices to bound the last term by 2 1000 . For this, note that the events E of1 , E deg , E bias , and E count1 are all determined by the randomness in Line 23, or equivalently by the graphs G [k] = G 1 , . . . , G k . Thus, it suffices to show that for any G [k] such that all the events E of1 , E deg , E bias , and E count1 occur, we have Pr E good | G [k] ≤ 1 1000 . Fix such a G [k] . By another union bound, we have: of2 , E count2 , (Lemmas 5.2 and 5.24) where the last inequality also uses the fact that E count2 and E of2 are determined by the randomness in Line 19 and therefore, independent of G [k] . To finish the proof, we show that for any choice of the randomness in Lines 19 and 23 such that the events count2 occur, the event E good also occurs. Fix such a randomness for the rest of the proof. Note that fixing this randomness fixes the value of all the random variables defined above and also fixes the value of all variables in Algorithms 3 and 4. Henceforth, we shall often abuse notation and use the name of the random variable to denote the value it is fixed to, e.g., X a,b,i,j is fixed to. We use a similar notation for variables. We first claim that, for all a, b ∈ [k] and i, j ∈ [ℓ], we have: (5.25) We prove Eq. (5.25) later but assuming it for now, we get from Lemmas 5.23 and 5.24 that (for all a, b ∈ [k] and i, j ∈ [ℓ]): Continuing using Lemmas 5.19 and 5.21, we get (for all a, b ∈ [k] and i, j ∈ [ℓ]): as desired. It remains to prove Eq. (5.25). We only show the second inequality as the proof for the first one is analogous. For this, fix a, b ∈ [k] and i, j ∈ [ℓ] and note from Eq. (4.3) that A(a, b, i, j) · p a p b q min{a,b} m = AEst a,b,i,j . Thus, it suffices to show that AEst a,b,i,j ≤ X G [k] ,+ a,b,i,j . For this, we first combine Line 36 with Item 2 of Lemma 5.16 to get: To continue, we claim that eStored min{a,b} ∩ (vEst a,i × vEst b,j ) = G min{a,b} ∩ (vEst a,i × vEst b,j ). As the ⊆ part is trivial, it suffices to show that ⊇ part. Fix any (u, v) ∈ G min{a,b} ∩ (vEst a,i × vEst b,j ).
Applying Item 3 of Lemma 5.3 implies that (u, v) ∈ eStored min{a,b} and we are done. With this claim, we get: Next, applying Item 1 of Lemma 5.16 to get vEst a,i × vEst b,j = V a,i ∩ S a × V b,j ∩ S b . The latter equals V a,i × V b,j ∩ (S a × S b ) and we get: To finish the proof, use Eqs. (5.17) and (5.22) and Lemma 5.15 to get 6 Analysis of the reduction: Proving Lemma 3.22 In this section, we prove several remaining lemmas from Section 3, which together will prove Lemma 3.22.

Basic properties of windows
We begin by stating a number of basic facts about windows (presented only for the necessary dimensions, for brevity).
• In four dimensions, for every w < k, ℓ ∈ N and a, b ∈ [k], i, j ∈ [ℓ], Fact 6.2 (Size difference of 1D windows). For every w ≤ w ′ < ℓ ∈ N and i ∈ [ℓ], Fact 6.3 (Symmetry of containment). Containment in windows is a symmetric property, i.e., • In two dimensions, for every w < ℓ ∈ N and i, j, i ′ , j ′ ∈ [ℓ], • In four dimensions, for every w < k, ℓ ∈ N and a, b, As a corollary, we have the following fact: Fact 6.4 (Counting containments). The number of windows a particular index is contained equals the size of its window, i.e., • In two dimensions, for every w < ℓ ∈ N and i ′ , j ′ ∈ [ℓ], the number of distinct windows • In four dimensions, for every w < k, ℓ ∈ N and The following is essentially the triangle inequality for the ∞-norm, and roughly states that "nearby windows look alike": Fact 6.5 (Triangle inequality for windows). For every w + w ′ < k, ℓ ∈ N, and every a, b, 6.2 Double-counting arguments: Proving Propositions 3.12 and 3.16 Proof of Proposition 3.12. We claim that the sum of entries in M ∼w is the same as in M . Indeed, this holds by Fact 6.4 and "double-counting". In particular, Proof of Proposition 3.16. Recall M = Proj(A) and N = Proj(A ∼w ). We first want to show M ∼w = N . Again, we can do this by "double-counting". Recall that Win w,k,ℓ (a, b, i, j) = Win w,k (a, b) × Win w,ℓ (i, j) (and thus ν ∼w,k,ℓ (a, b, i, j) = ν ∼w,k (a, b) · ν ∼w,ℓ (i, j)). We have:

"Smoothing graphs": Proving Lemma 3.13
In this section, we prove Lemma 3.13. We construct H based on G in two stages: First, we construct an intermediate (weighted) graph K by "blowing up" each vertex of G (which preserves biases of vertices and the Max-DICUT value). Then, we slightly modify K to form the (weighted) graph H by perturbing the bias at each vertex, and argue that this does not change the Max-DICUT value too much. We begin with some notation. We label the vertices of G by [n] = {1, . . . , n}. We assume WLOG that G has no isolated vertices (if not, we simply remove all isolated vertices and analyze the new graph; this doesn't affect BiasMat G,t or val G ).

Defining K via (weighted) blowups
First, given G, we construct a graph K as follows. For each vertex v ∈ [n], in K we create |Win w,ℓ (b-ind t G (v))| distinct vertices labeled {v} × Win w,ℓ (b-ind t G (v)). Thus, K has vertex-set V def = n v=1 {v} × Win w,ℓ (b-ind t G (v)). Now if AdjMat G (u, v) is the (positive) weight of an edge u → v in G, we divide its weight evenly among all the copies of u and v in K, i.e., we place weight 4. bias K (v, i ′ ) = bias G (v).
Further, m G = m K and val G = val K .
The proof is basically a series of double-counting arguments using the definition of K, and we defer it until the end of the section.

Constructing H via perturbations
Now, we construct H by modifying K. We begin with a new graph H 0 consisting of a copy of K and a new isolated vertex (⋆, ⋆), so that H 0 has vertex-set V ∪ {(⋆, ⋆)}, and let V * = v∈[n] ({v} × (Win w,ℓ (b-ind t G (v))) \ {b-ind t G (v)})) ⊆ V denote the set of vertices whose biases we'd like to modify. We let m 0 def = m G = m K = m H 0 denote the total weight in G, K, and H 0 (which coincide by Claim 6.8).
Next, we iteratively modify the biases of vertices using the following claim, which roughly lets us decrease the bias of a vertex (v, i ′ ) ∈ V * by increasing its in-degree and decreasing its out-degree, or increase the bias of a vertex by increasing its out-degree and decreasing its in-degree, "without modifying the graph too much". By definition, we have = n u,v=1 (i ′ ,j ′ )∈Win w,ℓ (b-ind t G (u,v)) Conversely, let y be any assignment for K. We construct a probabilistic assignment x by, for each vertex v ∈ [n], sampling i ′ ∈ Win w,ℓ (b-ind t G (v)) uniformly and independently at random, and setting x v = y (v,i ′ ) . This assignment has expected value which equals val K (y) by the previous calculation.
denote the (unnormalized) numbers of constraints satisfied by x in G and G spar , respectively; and g def = m · val G (x) = max x∈{0,1} n y(x) and g ′ def = m ′ · val Gspar (x) = max x∈{0,1} n y ′ (x) denote the (unnormalized) values of G and G', respectively.
For each e ∈ E let I e be the indicator random variable for the event that e survives in G spar . Thus, we can write m ′ and y ′ (x) as sums of independent Bern p random variables: Our first goal is to show that w.h.p., |g ′ − pg| ≤ ǫ spar pg/2.
Upper-bounding g ′ . To prove an upper bound on g ′ , we take a union bound over all assignments x ∈ {0, 1} n , and prove an o(2 −n ) bound on the probability that y ′ (x) ≥ (1 + ǫ spar /2)pg.
By assumption on p, this is at most 2 exp(−C spar n/12) which is o(1).
Putting the bounds together. It remains to prove a bound on |val G −val Gspar |. As in Section 6.5, we split into "real" and "normalization" error terms: The first term can be bounded by ǫ spar /2 since w.h.p. |g ′ − pg| ≤ ǫ spar pg/2 and g ≤ m. For the second, using g ′ ≤ m ′ the term becomes |m ′ /pm − 1| = |m ′ − pm|/(pm), which is at most ǫ spar /2 since |m ′ − pm| ≤ ǫ spar pm/2.