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 Emi Perdan Research Interests Algorithms and Complexity Security and Privacy Theory Advisees William He Noah Singer Jingxun Liang CSD Courses Taught 15251 - Fall, 2025 15754 - Spring, 2025 15459 - Fall, 2024 15751 - Spring, 2024 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 Publications Conference Explicit Two-Sided Vertex Expanders beyond the Spectral Barrier 2025 • Annual ACM Symposium on Theory of Computing • 833-842 Hsieh J-T, Lin T-C, Mohanty S, O'Donnell R, Zhang RY Conference Learning the Closest Product State 2025 • Annual ACM Symposium on Theory of Computing • 1212-1221 Bakshi A, Bostanci J, Kretschmer W, Landau Z, Li J, Liu A, O'Donnell R, Tang E Journal Article Quartic Quantum Speedups for Planted Inference 2025 • Physical Review X • 15(2):021077 Schmidhuber A, O’Donnell R, Kothari R, Babbush R Journal Article Welcome from the Program Chair 2024 • Annual ACM Symposium on Theory of Computing • iii-iv Mohar B, Shinkar I, O'Donnell R Conference Explicit orthogonal and unitary designs 2023 • Annual Symposium on Foundations of Computer Science • 00:1240-1260 O’Donnell R, Servedio RA, Paredes P
Conference Explicit Two-Sided Vertex Expanders beyond the Spectral Barrier 2025 • Annual ACM Symposium on Theory of Computing • 833-842 Hsieh J-T, Lin T-C, Mohanty S, O'Donnell R, Zhang RY
Conference Learning the Closest Product State 2025 • Annual ACM Symposium on Theory of Computing • 1212-1221 Bakshi A, Bostanci J, Kretschmer W, Landau Z, Li J, Liu A, O'Donnell R, Tang E
Journal Article Quartic Quantum Speedups for Planted Inference 2025 • Physical Review X • 15(2):021077 Schmidhuber A, O’Donnell R, Kothari R, Babbush R
Journal Article Welcome from the Program Chair 2024 • Annual ACM Symposium on Theory of Computing • iii-iv Mohar B, Shinkar I, O'Donnell R
Conference Explicit orthogonal and unitary designs 2023 • Annual Symposium on Foundations of Computer Science • 00:1240-1260 O’Donnell R, Servedio RA, Paredes P
