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. "The Weakness of CTC Qubits and the Power of Approximate Counting," Ryan O’Donnell, A. C. Cem Say, ACM Transactions on Computation Theory 10, 2 (2018). 
  2. "A log-Sobolev inequality for the multislice, with applications," Yuval Filmus, Ryan O’Donnell, Xinyu Wu, arXiv:1809.03546v1 (2018).
  3. "SOS lower bounds with hard constraints: think global, act local," Pravesh K. Kothari, Ryan O’Donnell, Tselil Schramm, arXiv:1809.01207v (2018). 
  4. "Fooling Polytopes," Ryan O’Donnell, Rocco A. Servedio, Li-Yang Tan, arXiv:1808.04035v1 (2018).
  5. "On closeness to k-wise uniformity," Ryan O’Donnell, Yu Zhao, arXiv:1806.03569v1 (2018). 

More Members