Dor Minzer, Institute for Advanced Study

Abstract

In the Max-Cut problem in the streaming model, an algorithm is given the edges of an unknown graph G = (V, E) in some fixed order, and its goal is to approximate the size of the largest cut in G. We show that any streaming algorithm achieving a non-trivial approximation ratio of 1/2+eps must either make polynomially many passes over the input, or else must have polynomial memory. This improves upon earlier result in the area that established similar lower bounds either on algorithms that a single pass on the input stream, or algorithms that achieve approximation ratio close to 1. Provided time, I will also discuss subsequent developments establishing a dichotomy theorem for all constraint satisfaction model in the multi-pass streaming model. Based on joint works with Yumou Fei and Shuo Wang.