Abstract: Polynomial-time approximation algorithms have been widely studied for constraint satisfaction problems (CSPs). In this setting, the prototypical problem is Max-CUT, whose approximability was (conditionally) settled in several seminal works. A more recent line of work explores CSP approximability in the purportedly weaker, and more information-theoretic, setting of streaming algorithms.
In the streaming setting, nontrivial approximations to Max-CUT have been ruled out in very strong models. Hence, attention has turned to the “next simplest” CSP: Max-DICUT, the variant of Max-CUT for directed graphs. Chou, Golovnev, and Velusamy settled Max-DICUT’s approximability in the small-space streaming regime: for all ε>0, 4/9-ε approximations are possible in O(log n) space, but 4/9+ε approximations require Ω(sqrt n) space.
We present a surprising simplification of the O(log n) space algorithm for Max-DICUT [1]. This leads naturally to a more general notion which we call a “snapshot” of a directed graph. We describe how snapshots can be measured by streaming algorithms, and how they in turn enable a 0.486-approximation to Max-DICUT in O-tilde(sqrt n) space [2]. (For comparison, 4/9≈0.445.) This work opens the way for a rich landscape of possibilities, both for space complexities beyond sqrt n, and for other CSPs beyond Max-DICUT.
Based on joint works with [1] Joanna Boyland, Michael Hwang, Tarun Prasad, and Santhoshini Velusamy (APPROX'22), and [2] Raghuvansh R. Saxena, Madhu Sudan, and Santhoshini Velusamy (SODA'23 and preprint).