Random MAX SAT, random MAX CUT, and their phase transitions.

Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin

Browse the full SODA paper archive.