Ryan O'Donnell
Alma mater
Known forAnalysis of Boolean functions[pub 1]
Scientific career
FieldsAnalysis of Boolean functions, Complexity theory, Computational learning theory, Hardness of approximation, Quantum computing
ThesisComputational applications of noise sensitivity (2003)
Doctoral advisorMadhu Sudan
Websitehttps://www.cs.cmu.edu/~odonnell/

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.[pub 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.[1] He then completed his Ph.D. at the Massachusetts Institute of Technology (MIT) in 2003, advised by Madhu Sudan.[2]

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

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[4] and on the scientific board of the Electronic Colloquium on Computational Complexity.[5]

O'Donnell operates a YouTube channel, which has 10.2k+ subscribers and 680k+ views as of December 2023.[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. 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

  1. 1 2 3 O'Donnell, Ryan (2014). Analysis of Boolean functions. New York: Cambridge University Press. arXiv:2105.10386. ISBN 978-1-107-03832-5.
  2. ↑ Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O’Donnell, Ryan (2007). "Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?". SIAM Journal on Computing. 37 (1): 319–357. doi:10.1137/S0097539705447372. ISSN 0097-5397. S2CID 2090495.
  3. ↑ Mossel, Elchanan; O’Donnell, Ryan; Oleszkiewicz, Krzysztof (2010-03-17). "Noise stability of functions with low influences: Invariance and optimality". Annals of Mathematics. 171 (1): 295–341. arXiv:math/0503503. doi:10.4007/annals.2010.171.295. ISSN 0003-486X.
  4. ↑ Polymath, D.H.J. (2012-05-01). "A new proof of the density Hales-Jewett theorem". Annals of Mathematics. 175 (3): 1283–1327. doi:10.4007/annals.2012.175.3.6. ISSN 0003-486X.
  5. ↑ Klivans, A.R.; O'Donnell, R.; Servedio, R.A. (2002). "Learning intersections and thresholds of halfspaces". The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. IEEE. pp. 177–186. doi:10.1109/SFCS.2002.1181894. ISBN 978-0-7695-1822-0. S2CID 1664758.
  6. ↑ O'Donnell, Ryan; Wright, John (2017-06-19). "Efficient quantum tomography II". Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. ACM. pp. 962–974. doi:10.1145/3055399.3055454. ISBN 978-1-4503-4528-6.

References

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.