An optimal space lower bound for approximating MAX-CUT.

Michael Kapralov, Dmitry Krachun

Browse the full STOC paper archive.