Random MAX SAT, Random MAX CUT, and Their Phase Transitions

Don Coppersmith, David Gamarnik, Mohammad Hajiaghayi +1

Given a 2-SAT formula $F$ consisting of $n$ variables and $\cn$ random clauses, what is the largest number of clauses $\max F$ satisfiable by a single assignment of the variables?…