Multi-Pass Streaming Lower Bounds for Approximating Max-Cut

Yumou Fei, Dor Minzer, Shuo Wang

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 l…