Streaming Complexity Separations for Dense and Sparse Graphs

Yang P. Liu, Hoai-An Nguyen, Noah G. Singer +1

We identify a sharp separation in the streaming space complexity of Maximum Cut when the algorithm must output an approximate cut (rather than only the approximate value). For dens…