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 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 Mean estimation when you have the source code; or, quantum Monte Carlo methods 2023 • Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms • 2023-January:1186-1215 Kothari R, O'Donnell R Conference Query-optimal estimation of unitary channels in diamond distance 2023 • Annual Symposium on Foundations of Computer Science • 363-390 Haah J, Kothari R, 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 Mean estimation when you have the source code; or, quantum Monte Carlo methods 2023 • Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms • 2023-January:1186-1215 Kothari R, O'Donnell R
Conference Query-optimal estimation of unitary channels in diamond distance 2023 • Annual Symposium on Foundations of Computer Science • 363-390 Haah J, Kothari R, O'Donnell R, Tang E
