Ryan O'Donnell is a Canadian theoretical computer scientist and a professor at

Carnegie Mellon University Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...

. He is known for his work on the analysis of Boolean functions and for authoring the textbook on this subject. He is also known for his work on computational learning theory,

hardness of approximation In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. Scope Hardness of approximation complements the study of approximation algorithms by pro ...

, property testing,

quantum computation Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...

and

quantum information Quantum information is the information of the state of a quantum system. It is the basic entity of study in quantum information theory, and can be manipulated using quantum information processing techniques. Quantum information refers to both th ...

. O'Donnell completed his B.Sc. in Mathematics and Computer Science at the

University of Toronto The University of Toronto (UToronto or U of T) is a public research university in Toronto, Ontario, Canada, located on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution ...

. He then completed his Ph.D. at the

Massachusetts Institute of Technology The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the ...

(MIT) in 2003, advised by

Madhu Sudan Madhu Sudan (born 12 September 1966) is an Indian-American computer scientist. He has been a Gordon McKay Professor of Computer Science at the Harvard John A. Paulson School of Engineering and Applied Sciences since 2015. Career He received ...

Research

O'Donnell proved that the Goemans–Williamson approximation algorithm for MAX-CUT is optimal, assuming the

unique games conjecture In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate ''value'' of a certain type of gam ...

. The proof follows from two papers, one in 2004 with Subhash Khot, Guy Kindler, and

Elchanan Mossel Elchanan Mossel ( he, אלחנן מוסל) is a professor of mathematics at the Massachusetts Institute of Technology. His primary research fields are probability theory, combinatorics, and statistical inference. Research Mossel's research spans ...

which reduced this statement to proving the Majority Is Stablest conjecture in analysis of Boolean functions, and one in 2005 with

and Krzysztof Oleszkiewicz which proves this conjecture. He later wrote an influential textbook on the analysis of Boolean functions. 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 In mathematics, the Hales–Jewett theorem is a fundamental combinatorial result of Ramsey theory named after Alfred W. Hales and Robert I. Jewett, concerning the degree to which high-dimensional objects must necessarily exhibit some combinatorial ...

, 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 The Electronic Colloquium on Computational Complexity (ECCC) is an electronic archive of research papers in computational complexity theory, a branch of computer science.... The intention of the ECCC is to provide a fast publication service interme ...

. O'Donnell operates a

YouTube YouTube is a global online video platform, online video sharing and social media, social media platform headquartered in San Bruno, California. It was launched on February 14, 2005, by Steve Chen, Chad Hurley, and Jawed Karim. It is owned by ...

channel, which has 10.2k+ subscribers and 680k+ views as of December 2023. On there, he delivers mathematics and computer science lectures on topics such as complexity theory,

spectral graph theory In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix ...

, 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

References

External links

Official website

Faculty page

YouTube channel
{{DEFAULTSORT:ODonnell, Ryan Living people Quantum information scientists Theoretical computer scientists Date of birth missing (living people) Computer scientists Year of birth missing (living people)