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 < 0.45 approximation algorithm due to Chou, Golovnev, 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, 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 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 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 Max-DICUT behaviour in graphs.