Publications by Ryan O'Donnell

Conference

Explicit Abelian Lifts and Quantum LDPC Codes

2022 • Leibniz International Proceedings in Informatics • 215:
Jeronimo FG, Mittal T, O'Donnell R, Paredes P, Tulsiani M

Journal Article

EXPLICIT NEAR-RAMANUJAN GRAPHS OF EVERY DEGREE

2022 • SIAM Journal on Computing • 51(3):1-23
Mohanty S, O'Donnell R, Paredes P

Conference

Fooling Polytopes

2022 • Journal of the ACM • 69(2):
O'donnell R, Servedio RA, Tan LY

Conference

Optimizing strongly interacting fermionic Hamiltonians

2022 • Annual ACM Symposium on Theory of Computing • 776-789
Hastings MB, O'Donnell R

Conference

The SDP Value of Random 2CSPs

2022 • Leibniz International Proceedings in Informatics • 229:
Musipatla A, O'Donnell R, Schramm T, Wu X

Conference

Fiber bundle codes: Breaking the n<sup>1/2</sup>polylog(n) barrier for Quantum LDPC codes

2021 • Annual ACM Symposium on Theory of Computing • 1276-1288
Hastings MB, Haah J, O'Donnell R

Conference

Improved Quantum data analysis

2021 • Annual ACM Symposium on Theory of Computing • 1398-1411
Badescu C, O'Donnell R

Conference

Pauli error estimation via population recovery

2021 • Leibniz International Proceedings in Informatics • 197:
Flammia ST, O'Donnell R

Conference

Quantum approximate counting with nonadaptive grover iterations

2021 • Leibniz International Proceedings in Informatics • 187:
Venkateswaran R, O'Donnell R

Journal Article

Editorial from the new editor-in-chief

2020 • ACM Transactions on Computation Theory • 12(1):
O'Donnell R

Conference

Explicit near-fully x-ramanujan graphs

2020 • Annual Symposium on Foundations of Computer Science • 2020-November:1045-1056
O'Donnell R, Wu X

Conference

Explicit near-Ramanujan graphs of every degree

2020 • Annual ACM Symposium on Theory of Computing • 510-523
Mohanty S, O'Donnell R, Paredes P

Conference

Fooling Gaussian PTFs via local hyperconcentration

2020 • Annual ACM Symposium on Theory of Computing • 1170-1183
O'Donnell R, Servedio RA, Tan LY

Conference

The SDP value for random two-eigenvalue CSPs

2020 • Leibniz International Proceedings in Informatics • 154:
Mohanty S, O'Donnell R, Paredes P

Conference

X-Ramanujan graphs

2020 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 2020-January:1226-1243
Mohanty S, O'Donnell R

Conference

On Closeness to k-wise uniformity

2018 • Leibniz International Proceedings in Informatics • 116:
O'Donnell R, Zhao Y

Conference

Bounding laconic proof systems by solving CSPs in parallel

2017 • Annual ACM Symposium on Parallelism in Algorithms and Architectures • Part F129316:95-99
Li J, O'Donnell R

Conference

Efficient quantum tomography II

2017 • Annual ACM Symposium on Theory of Computing • Part F128415:962-974
O'Donnell R, Wright J

Conference

Optimal mean-based algorithms for trace reconstruction

2017 • Annual ACM Symposium on Theory of Computing • Part F128415:1047-1056
De A, O'Donnell R, Servedio RA

Conference

Preface

2017 • Leibniz International Proceedings in Informatics • 79:
O'Donnell R

Conference

Quantum automata cannot detect biased coins, even in the limit

2017 • Leibniz International Proceedings in Informatics • 80:
Kindler G, O'Donnell R

Conference

SOS is not obviously automatizable, even approximately

2017 • Leibniz International Proceedings in Informatics • 67:
O'Donnell R

Conference

Sum of Squares Lower Bounds for Refuting any CSP

2017 • Annual ACM Symposium on Theory of Computing • 132-145
Kothari PK, Mori R, O'Donnell R, Witmer D

Journal Article

Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs

2016 • Stochastic Processes and their Applications • 126(9):2719-2733
Benjamini I, Chan SO, O'Donnell R, Tamuz O, Tan LY

Conference

Efficient quantum tomography

2016 • Annual ACM Symposium on Theory of Computing • 19-21-June-2016:899-912
O'Donnell R, Wright J