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. "Quantum state certification,"  C Badescu, R O'Donnell, and J Wright.  51st Annual ACM SIGACT Symposium on Theory of Computing (2019)
  2. "The SDP value for random two-eigenvalue CSP's,"  S Mohanty, R O'Donnell, and P Paredes.  arXiv 1906.06732 (2019)
  3. "Lower bounds for testing complete positivity and quantum separability," C Badescu and R O'DonnellarXiv 1905.01542 (2019)
  4. "X-Ramanujan Graph," S Mohanty and R O'DonnellarXiv 1904.03500
  5. "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.

More Members