Ryan O'Donnell

Publication Activity (10 Years)

Years Active: 2002-2024
Publications (10 Years): 82

Top Venues

CoRR

STOC

SODA

Electron. Colloquium Comput. Complex.

Publications

Alexander Schmidhuber, Ryan O'Donnell, Robin Kothari, Ryan Babbush
Quartic quantum speedups for planted inference. CoRR (2024)
William He, Ryan O'Donnell
Pseudorandom Permutations from Random Reversible Circuits. CoRR (2024)
Costin Badescu, Ryan O'Donnell
Improved quantum data analysis. TheoretiCS 3 (2024)
Jeongwan Haah, Robin Kothari, Ryan O'Donnell, Ewin Tang
Query-optimal estimation of unitary channels in diamond distance. FOCS (2023)
Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes
Explicit orthogonal and unitary designs. CoRR (2023)
Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes
Explicit orthogonal and unitary designs. FOCS (2023)
Robin Kothari, Ryan O'Donnell
Mean estimation when you have the source code; or, quantum Monte Carlo methods. SODA (2023)
Steven T. Flammia, Ryan O'Donnell
Quantum chi-squared tomography and mutual information testing. CoRR (2023)
Jeongwan Haah, Robin Kothari, Ryan O'Donnell, Ewin Tang
Query-optimal estimation of unitary channels in diamond distance. CoRR (2023)
Robin Kothari, Ryan O'Donnell
Mean estimation when you have the source code; or, quantum Monte Carlo methods. CoRR (2022)
Ryan O'Donnell, Kevin Pratt
High-Dimensional Expanders from Chevalley Groups. CCC (2022)
Matthew B. Hastings, Ryan O'Donnell
Optimizing strongly interacting fermionic Hamiltonians. STOC (2022)
Ryan O'Donnell, Ramgopal Venkateswaran
The Quantum Union Bound made easy. SOSA (2022)
Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, Madhur Tulsiani
Explicit Abelian Lifts and Quantum LDPC Codes. ITCS (2022)
Ryan O'Donnell, Kevin Pratt
High-Dimensional Expanders from Chevalley Groups. CoRR (2022)
Sitan Chen, Jerry Li, Ryan O'Donnell
Toward Instance-Optimal State Certification With Incoherent Measurements. COLT (2022)
Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
Explicit Near-Ramanujan Graphs of Every Degree. SIAM J. Comput. 51 (3) (2022)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Fooling Polytopes. J. ACM 69 (2) (2022)
Amulya Musipatla, Ryan O'Donnell, Tselil Schramm, Xinyu Wu
The SDP Value of Random 2CSPs. ICALP (2022)
Steven T. Flammia, Ryan O'Donnell
Pauli error estimation via Population Recovery. Quantum 5 (2021)
Anindya De, Ryan O'Donnell, Rocco A. Servedio
Learning sparse mixtures of permutations from noisy information. COLT (2021)
Costin Badescu, Ryan O'Donnell
Improved Quantum data analysis. STOC (2021)
Ryan O'Donnell
Analysis of Boolean Functions. CoRR (2021)
Matthew B. Hastings, Ryan O'Donnell
Optimizing Strongly Interacting Fermionic Hamiltonians. CoRR (2021)
Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, Madhur Tulsiani
Explicit Abelian Lifts and Quantum LDPC Codes. CoRR (2021)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan, Daniel Kane
Fooling Gaussian PTFs via Local Hyperconcentration. CoRR (2021)
Sitan Chen, Jerry Li, Ryan O'Donnell
Toward Instance-Optimal State Certification With Incoherent Measurements. CoRR (2021)
Amulya Musipatla, Ryan O'Donnell, Tselil Schramm, Xinyu Wu
The SDP value of random 2CSPs. CoRR (2021)
Ramgopal Venkateswaran, Ryan O'Donnell
Quantum Approximate Counting with Nonadaptive Grover Iterations. STACS (2021)
Ryan O'Donnell, Tselil Schramm
Sherali-Adams Strikes Back. Theory Comput. 17 (2021)
Matthew B. Hastings, Jeongwan Haah, Ryan O'Donnell
) barrier for Quantum LDPC codes. STOC (2021)
Steven T. Flammia, Ryan O'Donnell
Pauli Error Estimation via Population Recovery. TQC (2021)
Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
The SDP Value for Random Two-Eigenvalue CSPs. STACS (2020)
Matthew B. Hastings, Jeongwan Haah, Ryan O'Donnell
polylog(N) Barrier for Quantum LDPC Codes. CoRR (2020)
Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
Explicit near-Ramanujan graphs of every degree. STOC (2020)
Costin Badescu, Ryan O'Donnell
Improved quantum data analysis. CoRR (2020)
Ryan O'Donnell, Xinyu Wu
Explicit near-fully X-Ramanujan graphs. CoRR (2020)
Ryan O'Donnell
Editorial from the New Editor-in-Chief. ACM Trans. Comput. Theory 12 (1) (2020)
Anindya De, Ryan O'Donnell, Rocco A. Servedio
Sharp Bounds for Population Recovery. Theory Comput. 16 (2020)
Ryan O'Donnell, Xinyu Wu
Explicit near-fully X-Ramanujan graphs. FOCS (2020)
Sidhanth Mohanty, Ryan O'Donnell
-Ramanujan graphs. SODA (2020)
Costin Badescu, Ryan O'Donnell
Lower Bounds for Testing Complete Positivity and Quantum Separability. LATIN (2020)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Fooling Gaussian PTFs via local hyperconcentration. STOC (2020)
Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
Explicit near-Ramanujan graphs of every degree. CoRR (2019)
Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen
The threshold for SDP-refutation of random regular NAE-3SAT. SODA (2019)
Sidhanth Mohanty, Ryan O'Donnell
X-Ramanujan Graphs. CoRR (2019)
Ryan O'Donnell, Tselil Schramm
Sherali - Adams Strikes Back. Computational Complexity Conference (2019)
Yuval Filmus, Ryan O'Donnell, Xinyu Wu
A Log-Sobolev Inequality for the Multislice, with Applications. ITCS (2019)
Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
The SDP value for random two-eigenvalue CSPs. CoRR (2019)
Costin Badescu, Ryan O'Donnell, John Wright
Quantum state certification. STOC (2019)
Pravesh K. Kothari, Ryan O'Donnell, Tselil Schramm
SOS Lower Bounds with Hard Constraints: Think Global, Act Local. ITCS (2019)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Fooling polytopes. STOC (2019)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Fooling Polytopes. Electron. Colloquium Comput. Complex. 25 (2018)
Ryan O'Donnell, Yu Zhao
On Closeness to k-Wise Uniformity. APPROX-RANDOM (2018)
Ryan O'Donnell, A. C. Cem Say
The Weakness of CTC Qubits and the Power of Approximate Counting. ACM Trans. Comput. Theory 10 (2) (2018)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Fooling Polytopes. CoRR (2018)
Anindya De, Ryan O'Donnell, Rocco A. Servedio
Learning sparse mixtures of rankings from noisy information. CoRR (2018)
Ryan O'Donnell, Yu Zhao
On closeness to k-wise uniformity. CoRR (2018)
Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen
The threshold for SDP-refutation of random regular NAE-3SAT. CoRR (2018)
Pravesh Kothari, Ryan O'Donnell, Tselil Schramm
SOS lower bounds with hard constraints: think global, act local. CoRR (2018)
Yuval Filmus, Ryan O'Donnell, Xinyu Wu
A log-Sobolev inequality for the multislice, with applications. CoRR (2018)
Ryan O'Donnell, Tselil Schramm
Sherali-Adams Strikes Back. CoRR (2018)
Shachar Lovett, Ryan O'Donnell
Special Issue: CCC 2017: Guest Editor's Foreword. Theory Comput. 14 (1) (2018)
Anindya De, Ryan O'Donnell, Rocco A. Servedio
Sharp bounds for population recovery. CoRR (2017)
Guy Kindler, Ryan O'Donnell
Quantum Automata Cannot Detect Biased Coins, Even in the Limit. ICALP (2017)
Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer
Sum of squares lower bounds for refuting any CSP. CoRR (2017)
Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright
Improved NP-Inapproximability for 2-Variable Linear Equations. Theory Comput. 13 (1) (2017)
Costin Badescu, Ryan O'Donnell, John Wright
Quantum state certification. CoRR (2017)
Ryan O'Donnell
SOS Is Not Obviously Automatizable, Even Approximately. ITCS (2017)
Ryan O'Donnell, John Wright
Guest Column: A Primer on the Statistics of Longest Increasing Subsequences and Quantum States (Shortened Version). SIGACT News 48 (3) (2017)
Jason Li, Ryan O'Donnell
Bounding Laconic Proof Systems by Solving CSPs in Parallel. SPAA (2017)
Anindya De, Ryan O'Donnell, Rocco A. Servedio
Optimal mean-based algorithms for trace reconstruction. STOC (2017)
Ryan O'Donnell, John Wright
Efficient quantum tomography II. STOC (2017)
Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer
Sum of squares lower bounds for refuting any CSP. STOC (2017)
Guy Kindler, Ryan O'Donnell
Quantum automata cannot detect biased coins, even in the limit. CoRR (2016)
Ryan O'Donnell, John Wright
Efficient quantum tomography. STOC (2016)
Ryan O'Donnell, A. C. Cem Say
The weakness of CTC qubits and the power of approximate counting. Electron. Colloquium Comput. Complex. 23 (2016)
Anindya De, Ryan O'Donnell, Rocco A. Servedio
Optimal mean-based algorithms for trace reconstruction. CoRR (2016)
Jason Li, Ryan O'Donnell
Bounding laconic proof systems by solving CSPs in parallel. Electron. Colloquium Comput. Complex. 23 (2016)
Ryan O'Donnell, John Wright
Efficient quantum tomography II. CoRR (2016)
Ryan O'Donnell, Yu Zhao
Polynomial Bounds for Decoupling, with Applications. Computational Complexity Conference (2016)
Ryan O'Donnell
SOS is not obviously automatizable, even approximately. Electron. Colloquium Comput. Complex. 23 (2016)
Shaddin Dughmi, Nicole Immorlica, Ryan O'Donnell, Li-Yang Tan
Algorithmic Signaling of Features in Auction Design. SAGT (2015)
Ryan O'Donnell, John Wright
Quantum Spectrum Testing. STOC (2015)
Ryan O'Donnell, John Wright
Efficient quantum tomography. CoRR (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR (2015)
Sarah R. Allen, Ryan O'Donnell
Conditioning and covariance on caterpillars. ITW (2015)
Guy Kindler, Ryan O'Donnell, David Witmer
Continuous analogues of the Most Informative Function problem. CoRR (2015)
Sarah R. Allen, Ryan O'Donnell, David Witmer
How to Refute a Random CSP. FOCS (2015)
Ryan O'Donnell, Yi Wu, Yuan Zhou
Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups. ACM Trans. Comput. Theory 7 (2) (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. Electron. Colloquium Comput. Complex. 22 (2015)
Cafer Caferov, Baris Kaya, Ryan O'Donnell, A. C. Cem Say
Optimal Bounds for Estimating Entropy with PMF Queries. MFCS (2) (2015)
Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright
Improved NP-Inapproximability for 2-Variable Linear Equations. APPROX-RANDOM (2015)
Sarah R. Allen, Ryan O'Donnell, David Witmer
How to refute a random CSP. CoRR (2015)
Ryan O'Donnell, Yu Zhao
Polynomial bounds for decoupling, with applications. CoRR (2015)
Ryan O'Donnell, A. C. Cem Say
One time-travelling bit is as good as logarithmically many. Electron. Colloquium Comput. Complex. 21 (2014)
Ryan O'Donnell, John Wright, Chenggang Wu, Yuan Zhou
Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs. CoRR (2014)
Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright
New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover. ACM Trans. Comput. Theory 6 (1) (2014)
Ryan O'Donnell
Social choice, computational complexity, Gaussian geometry, and Boolean functions. CoRR (2014)

Ryan O'Donnell.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Ryan O'Donnell