Ryan O'Donnell

Professor

Office 7213 Gates and Hillman Centers

Email odonnell@cs.cmu.edu

Phone (412) 268-4802

Department
Computer Science Department

Administrative Support Person
Oliver Moss

Research Interests
Algorithms and Complexity
Security and Privacy
Theory

Advisees
Kevin Pratt

CSD Courses Taught

15750 - Spring, 2023

Research Statement

 

My research interests are:

  • Fourier Analysis of Boolean functions

  • Constraint satisfaction problems: random instances and inapproximability

  • Quantum computation and information theory

  • Complexity theory, especially concrete complexity and proof complexity

  • Probability theory

  • Property testing and learning theory

 

Recent Publications

Jeronimo FG, Mittal T, O'Donnell R, Paredes P, Tulsiani M ( 2022 ) Leibniz International Proceedings in Informatics, LIPIcs, Explicit Abelian Lifts and Quantum LDPC Codes Vol: 215

Ryan O'Donnell ( 2022 ) SIAM Journal on Computing, EXPLICIT NEAR-RAMANUJAN GRAPHS OF EVERY DEGREE , Vol: 51 Issue: ( 3 ) , Page(s): 1- 23 .

O'donnell R, Servedio RA, Tan LY ( 2022 ) Journal of the ACM, Fooling Polytopes Vol: 69 Issue: ( 2 )

Hastings MB, O'Donnell R ( 2022 ) Proceedings of the Annual ACM Symposium on Theory of Computing, Optimizing strongly interacting fermionic Hamiltonians , Page(s): 776 - 789

Musipatla A, O'Donnell R, Schramm T, Wu X ( 2022 ) Leibniz International Proceedings in Informatics, LIPIcs, The SDP Value of Random 2CSPs Vol: 229