| Fields: | Analysis of Boolean functions, Complexity theory, Computational learning theory, Hardness of approximation, Quantum computing |
| Alma Mater: |
|
| Website: | https://www.cs.cmu.edu/~odonnell/ |
| Doctoral Advisor: | Madhu Sudan |
| Thesis Title: | Computational applications of noise sensitivity |
| Thesis Year: | 2003 |
| Thesis Url: | https://www.cs.cmu.edu/~odonnell/papers/thesis.pdf |
| Known For: | Analysis of Boolean functions |
Ryan O'Donnell is a Canadian theoretical computer scientist and a professor at Carnegie Mellon University. He is known for his work on the analysis of Boolean functions and for authoring the textbook on this subject.[1] He is also known for his work on computational learning theory, hardness of approximation, property testing, quantum computation and quantum information.
O'Donnell completed his B.Sc. in Mathematics and Computer Science at the University of Toronto.[2] He then completed his Ph.D. at the Massachusetts Institute of Technology (MIT) in 2003, advised by Madhu Sudan.
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,[3] and one in 2005 with Elchanan Mossel and Krzysztof Oleszkiewicz which proves this conjecture.[4] He later wrote an influential textbook on the analysis of Boolean functions.[1]
O'Donnell's other notable contributions include participation in the first Polymath project, Polymath1, for developing a combinatorial proof to the density Hales–Jewett theorem,[5] [6] improved algorithms for problems in computational learning theory,[7] and improved algorithms for the tomography of quantum states.[8]
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.
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[9] and on the scientific board of the Electronic Colloquium on Computational Complexity.[10]
O'Donnell operates a YouTube channel, which has 10.2k+ subscribers and 680k+ views as of December 2023.[11] 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.