Ryan O'Donnell

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