Half-Approximating Maximum Dicut in the Streaming Setting

This talk is based on joint work with Soheil Behnezhad, Shane Ferrante, and Mohammad Saneian, to appear at STOC'26. We study streaming algorithms for the maximum directed cut problem. The edges of an n-vertex directed graph arrive one by one in an arbitrary order, and the goal is to estimate the value of the maximum directed cut using a single pass and small space. With O(n) space, a (1−ε)-approximation can be trivially obtained for any fixed ε>0 using additive cut sparsifiers. The question that has attracted significant attention in the literature is the best approximation achievable by algorithms that use truly sublinear (i.e., n^{1−Ω(1)}) space.

 

A lower bound of Kapralov and Krachun (STOC'20) implies .5-approximation is the best one can hope for. The current best algorithm for general graphs obtains a .485-approximation due to the work of Saxena, Singer, Sudan, and Velusamy (FOCS'23). The same authors later obtained a (1/2−ε)-approximation, assuming that the graph is constant-degree (SODA'25).

 

In this paper, we show that for any ε>0, a (1/2−ε)-approximation of the maximum dicut value can be obtained with n^{1−Ω_ε(1)} space in general graphs. This shows that the lower bound of Kapralov and Krachun is generally tight, settling the approximation complexity of this fundamental problem. The key to our result is a careful analysis of how correlation propagates among high- and low-degree vertices, when simulating a suitable local algorithm.