Ryan O'Donnell

Department of Computer Science, Carnegie Mellon University
Ph.D. in Applied Mathematics, Massachusetts Institute of Technology, 2003

My research is in the areas of quantum computation, quantum complexity theory, and quantum information.  I am particularly interested in the mathematical theory of quantum tomography, as well as related problems concerning testing, certifying, and learning quantum states with low sample complexity and computational complexity.  I like to apply a wide range of mathematical tools (representation theory, probability, combinatorics, Fourier analysis) when attacking problems in the theory of quantum computation and quantum information.

Most Cited Publications
  1. "Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?," Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell, SIAM J. Comput.,37, 319 (2007)
  2. "Analysis of Boolean Functions," Ryan O’Donnell,Cambridge University Press (2014).
  3. "Noise stability of functions with low influences: invariance and optimality,"Elchanan Mossel, Ryan O'Donnell, Krzysztof Oleszkiewicz, FOCS 171, 295 (2005).
  4. "Learning functions of k relevant variables," Elchanan Mossel, Ryan O’Donnell, and Rocco A. Servedioc, Journal of Computer and System Sciences 69, 421 (2004).
  5. "Learning intersections and thresholds of halfspaces," Adam R. Klivans, Ryan O’Donnell, and Rocco A. Servedio, Journal of Computer and System Sciences 68, 808 (2004).
Recent Publications
  1. "Optimal mean-based algorithms for trace reconstruction." De, Anindya, Ryan O’Donnell, and Rocco A. Servedio. The Annals of Applied Probability 29, no. 2 (2019): 851-874.
  2. "The threshold for SDP-refutation of random regular NAE-3SAT." Deshpande, Yash, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, and Subhabrata Sen. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2305-2321. Society for Industrial and Applied Mathematics (2019).
  3. "Learning sparse mixtures of rankings from noisy information." De, Anindya, Ryan O'Donnell, and Rocco Servedio. arXiv preprint arXiv:1811.01216 (2018).
  4. "A log-Sobolev inequality for the multislice, with applications." Filmus, Yuval, Ryan O'Donnell, and Xinyu Wu. arXiv preprint arXiv:1809.03546 (2018).
  5. "SOS lower bounds with hard constraints: think global, act local." Kothari, Pravesh, Ryan O'Donnell, and Tselil Schramm. arXiv preprint arXiv:1809.01207 (2018).

More Members