(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space.

Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker

Browse the full SODA paper archive.