Ryan O'Donnell

Research

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, and one in 2005 with Elchanan Mossel and Krzysztof Oleszkiewicz which proves this conjecture. He later wrote an influential textbook on the analysis of Boolean functions. improved algorithms for problems in computational learning theory, and improved algorithms for the tomography of quantum states.

Recognition

He received the National Science Foundation CAREER Award in 2008 and a Sloan Research Fellowship in 2009. He gave an invited lecture at the International Congress of Mathematicians in 2014.

Service

O'Donnell served as the editor-in-chief for the journal ACM Transactions on Computation Theory from 2019 to 2023 and was an editor of the SIAM Journal on Discrete Mathematics from 2012 to 2017. He is on the scientific advisory board of the Simons Institute for the Theory of Computing and on the scientific board of the Electronic Colloquium on Computational Complexity.

O'Donnell operates a YouTube channel, which has 13.4k+ subscribers and 947k+ views as of May 2026. 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. He has directed several course series, such as his "CS Theory Toolkit" series, where he explores mathematical areas applicable to the theoretical computer science field.

Selected publications