Improved streaming algorithms for Max-DICUT via local snapshots

Given a directed graph, the Maximum Directed Cut (Max-DICUT) problem asks to estimate the size of the largest directed cut, an ordered partition of the vertex set whose size is given by the number of edges from one set to the other. Max-DICUT is central to the study of Constraint Satisfaction Problems (CSPs) in the streaming setting. The best achievable approximation for Max-DICUT in sub-polynomial (i.e., o(√n)) space is 4/9. This is achieved by a log space algorithm that computes a quantity called the bias of the graph via a black-box use of streaming 𝓁1 norm-estimation algorithm and outputs a 4/9 approximation to the Max-DICUT value using this bias. In this talk, I will describe more sophisticated algorithms that beat this 4/9 approximation in o(n) space by computing certain local snapshots of the graph. The talk will be based on joint works with Raghuvansh Saxena, Noah Singer, and Madhu Sudan.