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 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 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 Conference Explicit Abelian Lifts and Quantum LDPC Codes 2022 • Leibniz International Proceedings in Informatics • 215: Jeronimo FG, Mittal T, O'Donnell R, Paredes P, Tulsiani M Journal Article Explicit Near-Ramanujan Graphs of Every Degree 2022 • SIAM journal on computing (Print) • 51(3):stoc20-1-stoc20-23 Mohanty S, O'Donnell R, Paredes P
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
Conference Explicit Abelian Lifts and Quantum LDPC Codes 2022 • Leibniz International Proceedings in Informatics • 215: Jeronimo FG, Mittal T, O'Donnell R, Paredes P, Tulsiani M
Journal Article Explicit Near-Ramanujan Graphs of Every Degree 2022 • SIAM journal on computing (Print) • 51(3):stoc20-1-stoc20-23 Mohanty S, O'Donnell R, Paredes P
