Streaming Lower Bounds for Approximating MAX-CUT.

Michael Kapralov, Sanjeev Khanna, Madhu Sudan

Browse the full SODA paper archive.