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, Ryan O’Donnell. SIAM Journal on Computing.
  2. "Analysis of boolean functions." Ryan O'Donnell. Cambridge University Press.
  3. "Noise stability of functions with low influences: invariance and optimality." Elchanan Mossel, Ryan O'Donnell, Krzysztof Oleszkiewicz. FOCS 2005.
  4. "Learning functions of k relevant variables." Elchanan Mossel, Ryan O'Donnell, Rocco A Servedio. Journal of Computer and System Sciences.
  5. "Learning intersections and thresholds of halfspaces." Adam R Klivans, Ryan O'Donnell, Rocco A Servedio. Journal of Computer and System Sciences.
Recent Publications
  1. "Explicit near-Ramanujan graphs of every degree." Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes. arXiv preprint arXiv:1909.06988.
  2. "Quantum state certification." Costin Bădescu, Ryan O'Donnell, John Wright. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing.
  3. "The SDP value for random two-eigenvalue CSPs." Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes. arXiv preprint arXiv:1906.06732.
  4. "Lower bounds for testing complete positivity and quantum separability." Costin Bădescu, Ryan O'Donnell. arXiv preprint arXiv:1905.01542.
  5. "-Ramanujan Graphs." Sidhanth Mohanty, Ryan O'Donnell. arXiv preprint arXiv:1904.03500.

More Members