Ryan O'Donnell is a Canadian theoretical computer scientist and a professor at Carnegie Mellon University.
[2] O'Donnell proved that the Goemans–Williamson approximation algorithm for MAX-CUT is optimal, assuming the unique games conjecture.
The proof follows from two papers, one in 2004 with Subhash Khot, Guy Kindler, and Elchanan Mossel which reduced this statement to proving the Majority Is Stablest conjecture in analysis of Boolean functions,[pub 2] and one in 2005 with Elchanan Mossel and Krzysztof Oleszkiewicz which proves this conjecture.
[pub 6] He received the National Science Foundation CAREER Award in 2008 and a Sloan Research Fellowship in 2009.
[6] On there, he delivers mathematics and computer science lectures on topics such as complexity theory, spectral graph theory, and analysis of boolean functions, as well as uploads lectures from his classes at Carnegie Mellon University.