Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDRyan O'Donnell
Person information
- affiliation: Carnegie Mellon University, Pittsburgh, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
[c93]Robin Kothari, Ryan O'Donnell:
Mean estimation when you have the source code; or, quantum Monte Carlo methods. SODA 2023: 1186-1215- [i62]Jeongwan Haah, Robin Kothari, Ryan O'Donnell, Ewin Tang:
Query-optimal estimation of unitary channels in diamond distance. CoRR abs/2302.14066 (2023) - 2022
- [j34]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Fooling Polytopes. J. ACM 69(2): 9:1-9:37 (2022) - [c92]Ryan O'Donnell, Kevin Pratt:
High-Dimensional Expanders from Chevalley Groups. CCC 2022: 18:1-18:26 - [c91]Sitan Chen, Jerry Li, Ryan O'Donnell:
Toward Instance-Optimal State Certification With Incoherent Measurements. COLT 2022: 2541-2596 - [c90]Amulya Musipatla, Ryan O'Donnell, Tselil Schramm
, Xinyu Wu:
The SDP Value of Random 2CSPs. ICALP 2022: 97:1-97:19 - [c89]Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, Madhur Tulsiani:
Explicit Abelian Lifts and Quantum LDPC Codes. ITCS 2022: 88:1-88:21 - [c88]Ryan O'Donnell, Ramgopal Venkateswaran:
The Quantum Union Bound made easy. SOSA 2022: 314-320 - [c87]Matthew B. Hastings, Ryan O'Donnell:
Optimizing strongly interacting fermionic Hamiltonians. STOC 2022: 776-789 - [i61]Ryan O'Donnell, Kevin Pratt:
High-Dimensional Expanders from Chevalley Groups. CoRR abs/2203.03705 (2022) - [i60]Robin Kothari, Ryan O'Donnell:
Mean estimation when you have the source code; or, quantum Monte Carlo methods. CoRR abs/2208.07544 (2022) - 2021
- [j33]Steven T. Flammia, Ryan O'Donnell:
Pauli error estimation via Population Recovery. Quantum 5: 549 (2021) - [j32]Ryan O'Donnell, Tselil Schramm:
Sherali-Adams Strikes Back. Theory Comput. 17: 1-30 (2021) - [c86]Anindya De, Ryan O'Donnell, Rocco A. Servedio:
Learning sparse mixtures of permutations from noisy information. COLT 2021: 1429-1466 - [c85]Ramgopal Venkateswaran, Ryan O'Donnell:
Quantum Approximate Counting with Nonadaptive Grover Iterations. STACS 2021: 59:1-59:12 - [c84]Matthew B. Hastings, Jeongwan Haah, Ryan O'Donnell:
Fiber bundle codes: breaking the n1/2 polylog(n) barrier for Quantum LDPC codes. STOC 2021: 1276-1288 - [c83]Costin Badescu, Ryan O'Donnell:
Improved Quantum data analysis. STOC 2021: 1398-1411 - [c82]Steven T. Flammia, Ryan O'Donnell:
Pauli Error Estimation via Population Recovery. TQC 2021: 8:1-8:16 - [i59]Sitan Chen, Jerry Li, Ryan O'Donnell:
Toward Instance-Optimal State Certification With Incoherent Measurements. CoRR abs/2102.13098 (2021) - [i58]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan, Daniel Kane:
Fooling Gaussian PTFs via Local Hyperconcentration. CoRR abs/2103.07809 (2021) - [i57]Ryan O'Donnell:
Analysis of Boolean Functions. CoRR abs/2105.10386 (2021) - [i56]Amulya Musipatla, Ryan O'Donnell, Tselil Schramm, Xinyu Wu:
The SDP value of random 2CSPs. CoRR abs/2108.01038 (2021) - [i55]Matthew B. Hastings, Ryan O'Donnell:
Optimizing Strongly Interacting Fermionic Hamiltonians. CoRR abs/2110.10701 (2021) - [i54]Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, Madhur Tulsiani:
Explicit Abelian Lifts and Quantum LDPC Codes. CoRR abs/2112.01647 (2021) - 2020
- [j31]Anindya De, Ryan O'Donnell, Rocco A. Servedio:
Sharp Bounds for Population Recovery. Theory Comput. 16: 1-20 (2020) - [j30]Ryan O'Donnell:
Editorial from the New Editor-in-Chief. ACM Trans. Comput. Theory 12(1): 1e:1 (2020) - [c81]Ryan O'Donnell, Xinyu Wu:
Explicit near-fully X-Ramanujan graphs. FOCS 2020: 1045-1056 - [c80]Costin Badescu, Ryan O'Donnell:
Lower Bounds for Testing Complete Positivity and Quantum Separability. LATIN 2020: 375-386 - [c79]Sidhanth Mohanty, Ryan O'Donnell:
X-Ramanujan graphs. SODA 2020: 1226-1243 - [c78]Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes:
The SDP Value for Random Two-Eigenvalue CSPs. STACS 2020: 50:1-50:45 - [c77]Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes:
Explicit near-Ramanujan graphs of every degree. STOC 2020: 510-523 - [c76]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Fooling Gaussian PTFs via local hyperconcentration. STOC 2020: 1170-1183 - [i53]Ryan O'Donnell, Xinyu Wu:
Explicit near-fully X-Ramanujan graphs. CoRR abs/2009.02595 (2020) - [i52]Matthew B. Hastings, Jeongwan Haah, Ryan O'Donnell:
Fiber Bundle Codes: Breaking the N1/2 polylog(N) Barrier for Quantum LDPC Codes. CoRR abs/2009.03921 (2020)
2010 – 2019
- 2019
- [c75]Ryan O'Donnell, Tselil Schramm:
Sherali - Adams Strikes Back. CCC 2019: 8:1-8:30 - [c74]Yuval Filmus, Ryan O'Donnell, Xinyu Wu:
A Log-Sobolev Inequality for the Multislice, with Applications. ITCS 2019: 34:1-34:12 - [c73]Pravesh K. Kothari, Ryan O'Donnell, Tselil Schramm:
SOS Lower Bounds with Hard Constraints: Think Global, Act Local. ITCS 2019: 49:1-49:21 - [c72]Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen:
The threshold for SDP-refutation of random regular NAE-3SAT. SODA 2019: 2305-2321 - [c71]Costin Badescu, Ryan O'Donnell, John Wright:
Quantum state certification. STOC 2019: 503-514 - [c70]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Fooling polytopes. STOC 2019: 614-625 - [i51]Sidhanth Mohanty, Ryan O'Donnell:
X-Ramanujan Graphs. CoRR abs/1904.03500 (2019) - [i50]Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes:
The SDP value for random two-eigenvalue CSPs. CoRR abs/1906.06732 (2019) - [i49]Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes:
Explicit near-Ramanujan graphs of every degree. CoRR abs/1909.06988 (2019) - 2018
- [j29]Shachar Lovett, Ryan O'Donnell:
Special Issue: CCC 2017: Guest Editor's Foreword. Theory Comput. 14(1): 1-2 (2018) - [j28]Ryan O'Donnell, A. C. Cem Say:
The Weakness of CTC Qubits and the Power of Approximate Counting. ACM Trans. Comput. Theory 10(2): 5:1-5:22 (2018) - [c69]Ryan O'Donnell, Yu Zhao:
On Closeness to k-Wise Uniformity. APPROX-RANDOM 2018: 54:1-54:19 - [i48]Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen:
The threshold for SDP-refutation of random regular NAE-3SAT. CoRR abs/1804.05230 (2018) - [i47]Ryan O'Donnell, Yu Zhao:
On closeness to k-wise uniformity. CoRR abs/1806.03569 (2018) - [i46]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Fooling Polytopes. CoRR abs/1808.04035 (2018) - [i45]Pravesh Kothari, Ryan O'Donnell, Tselil Schramm:
SOS lower bounds with hard constraints: think global, act local. CoRR abs/1809.01207 (2018) - [i44]Yuval Filmus, Ryan O'Donnell, Xinyu Wu:
A log-Sobolev inequality for the multislice, with applications. CoRR abs/1809.03546 (2018) - [i43]Anindya De, Ryan O'Donnell, Rocco A. Servedio:
Learning sparse mixtures of rankings from noisy information. CoRR abs/1811.01216 (2018) - [i42]Ryan O'Donnell, Tselil Schramm:
Sherali-Adams Strikes Back. CoRR abs/1812.09967 (2018) - [i41]Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Fooling Polytopes. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j27]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): 37-59 (2017) - [j26]Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright:
Improved NP-Inapproximability for 2-Variable Linear Equations. Theory Comput. 13(1): 1-51 (2017) - [c68]Guy Kindler, Ryan O'Donnell:
Quantum Automata Cannot Detect Biased Coins, Even in the Limit. ICALP 2017: 15:1-15:8 - [c67]Ryan O'Donnell:
SOS Is Not Obviously Automatizable, Even Approximately. ITCS 2017: 59:1-59:10 - [c66]Jason Li, Ryan O'Donnell:
Bounding Laconic Proof Systems by Solving CSPs in Parallel. SPAA 2017: 95-100 - [c65]Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer:
Sum of squares lower bounds for refuting any CSP. STOC 2017: 132-145 - [c64]Ryan O'Donnell, John Wright:
Efficient quantum tomography II. STOC 2017: 962-974 - [c63]Anindya De, Ryan O'Donnell, Rocco A. Servedio:
Optimal mean-based algorithms for trace reconstruction. STOC 2017: 1047-1056 - [e1]Ryan O'Donnell:
32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia. LIPIcs 79, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2017, ISBN 978-3-95977-040-8 [contents] - [i40]Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer:
Sum of squares lower bounds for refuting any CSP. CoRR abs/1701.04521 (2017) - [i39]Anindya De, Ryan O'Donnell, Rocco A. Servedio:
Sharp bounds for population recovery. CoRR abs/1703.01474 (2017) - [i38]Costin Badescu, Ryan O'Donnell, John Wright:
Quantum state certification. CoRR abs/1708.06002 (2017) - 2016
- [c62]Ryan O'Donnell, Yu Zhao:
Polynomial Bounds for Decoupling, with Applications. CCC 2016: 24:1-24:18 - [c61]Ryan O'Donnell, John Wright:
Efficient quantum tomography. STOC 2016: 899-912 - [i37]Guy Kindler, Ryan O'Donnell:
Quantum automata cannot detect biased coins, even in the limit. CoRR abs/1610.03543 (2016) - [i36]Ryan O'Donnell, John Wright:
Efficient quantum tomography II. CoRR abs/1612.00034 (2016) - [i35]Anindya De, Ryan O'Donnell, Rocco A. Servedio:
Optimal mean-based algorithms for trace reconstruction. CoRR abs/1612.03148 (2016) - [i34]Jason Li, Ryan O'Donnell:
Bounding laconic proof systems by solving CSPs in parallel. Electron. Colloquium Comput. Complex. TR16 (2016) - [i33]Ryan O'Donnell:
SOS is not obviously automatizable, even approximately. Electron. Colloquium Comput. Complex. TR16 (2016) - [i32]Ryan O'Donnell, A. C. Cem Say:
The weakness of CTC qubits and the power of approximate counting. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j25]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): 9:1-9:16 (2015) - [c60]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: 110-123 - [c59]Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright:
Improved NP-Inapproximability for 2-Variable Linear Equations. APPROX-RANDOM 2015: 341-360 - [c58]Sarah R. Allen, Ryan O'Donnell, David Witmer:
How to Refute a Random CSP. FOCS 2015: 689-708 - [c57]Sarah R. Allen, Ryan O'Donnell:
Conditioning and covariance on caterpillars. ITW 2015: 1-5 - [c56]Cafer Caferov, Baris Kaya, Ryan O'Donnell, A. C. Cem Say:
Optimal Bounds for Estimating Entropy with PMF Queries. MFCS (2) 2015: 187-198 - [c55]Shaddin Dughmi, Nicole Immorlica, Ryan O'Donnell, Li-Yang Tan:
Algorithmic Signaling of Features in Auction Design. SAGT 2015: 150-162 - [c54]Ryan O'Donnell, John Wright:
Quantum Spectrum Testing. STOC 2015: 529-538 - [i31]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 abs/1505.03424 (2015) - [i30]Sarah R. Allen, Ryan O'Donnell, David Witmer:
How to refute a random CSP. CoRR abs/1505.04383 (2015) - [i29]Guy Kindler, Ryan O'Donnell, David Witmer:
Continuous analogues of the Most Informative Function problem. CoRR abs/1506.03167 (2015) - [i28]Ryan O'Donnell, John Wright:
Efficient quantum tomography. CoRR abs/1508.01907 (2015) - [i27]Ryan O'Donnell, Yu Zhao:
Polynomial bounds for decoupling, with applications. CoRR abs/1512.01603 (2015) - [i26]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. TR15 (2015) - 2014
- [b1]Ryan O'Donnell:
Analysis of Boolean Functions. Cambridge University Press 2014, ISBN 978-1-10-703832-5, pp. I-XX, 1-423 - [j24]Lap Chi Lau, Tal Malkin, Ryan O'Donnell, Luca Trevisan:
Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010). SIAM J. Comput. 43(1): 255 (2014) - [j23]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): 2:1-2:20 (2014) - [j22]Ryan O'Donnell, Yi Wu, Yuan Zhou:
Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny). ACM Trans. Comput. Theory 6(1): 5:1-5:13 (2014) - [c53]Ryan O'Donnell, David Witmer:
Goldreich's PRG: Evidence for Near-Optimal Polynomial Stretch. CCC 2014: 1-12 - [c52]Ryan O'Donnell, John Wright, Yu Zhao, Xiaorui Sun, Li-Yang Tan:
A Composition Theorem for Parity Kill Number. CCC 2014: 144-154 - [c51]Ryan O'Donnell, A. C. Cem Say:
One Time-traveling Bit is as Good as Logarithmically Many. FSTTCS 2014: 469-480 - [c50]Pravesh Kothari, Amir Nayyeri, Ryan O'Donnell, Chenggang Wu:
Testing Surface Area. SODA 2014: 1204-1214 - [c49]Manuel Kauers, Ryan O'Donnell, Li-Yang Tan, Yuan Zhou:
Hypercontractive inequalities via SOS, and the Frankl-Rödl graph. SODA 2014: 1644-1658 - [c48]Ryan O'Donnell, John Wright, Chenggang Wu, Yuan Zhou:
Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs. SODA 2014: 1659-1677 - [i25]Ryan O'Donnell, John Wright, Chenggang Wu, Yuan Zhou:
Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs. CoRR abs/1401.2436 (2014) - [i24]Sarah R. Allen, Ryan O'Donnell:
Conditioning and covariance on caterpillars. CoRR abs/1407.4423 (2014) - [i23]Ryan O'Donnell:
Social choice, computational complexity, Gaussian geometry, and Boolean functions. CoRR abs/1407.7763 (2014) - [i22]Ryan O'Donnell, A. C. Cem Say:
One time-travelling bit is as good as logarithmically many. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j21]Ryan O'Donnell, Karl Wimmer:
KKL, Kruskal-Katona, and Monotone Nets. SIAM J. Comput. 42(6): 2375-2399 (2013) - [j20]Elchanan Mossel, Ryan O'Donnell:
Special Issue on Analysis of Boolean Functions: Guest Editors' Foreword. Theory Comput. 9: 579-585 (2013) - [c47]Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan:
Learning Sums of Independent Integer Random Variables. FOCS 2013: 217-226 - [c46]Ryan O'Donnell, Li-Yang Tan:
A Composition Theorem for the Fourier Entropy-Influence Conjecture. ICALP (1) 2013: 780-791 - [c45]Ryan O'Donnell, Yuan Zhou:
Approximability and proof complexity. SODA 2013: 1537-1556 - [i21]Ryan O'Donnell, Li-Yang Tan:
A composition theorem for the Fourier Entropy-Influence conjecture. CoRR abs/1304.1347 (2013) - [i20]Ryan O'Donnell, Xiaorui Sun, Li-Yang Tan, John Wright, Yu Zhao:
A composition theorem for parity kill number. CoRR abs/1312.2143 (2013) - 2012
- [j19]Guy Kindler, Anup Rao, Ryan O'Donnell, Avi Wigderson:
Spherical cubes: optimal foams from computational hardness amplification. Commun. ACM 55(10): 90-97 (2012) - [j18]Ankur Moitra, Ryan O'Donnell:
Pareto Optimal Solutions for Smoothed Analysts. SIAM J. Comput. 41(5): 1266-1284 (2012) - [c44]Per Austrin, Ryan O'Donnell, John Wright:
A New Point of NP-Hardness for 2-to-1 Label Cover. APPROX-RANDOM 2012: 1-12 - [c43]Guy Kindler, Ryan O'Donnell:
Gaussian Noise Sensitivity and Fourier Tails. CCC 2012: 137-147 - [c42]Gábor Kun, Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida, Yuan Zhou:
Linear programming, width-1 CSPs, and robust satisfaction. ITCS 2012: 484-495 - [c41]Ryan O'Donnell, John Wright:
A new point of NP-hardness for unique games. STOC 2012: 289-306 - [i19]Ryan O'Donnell, David Witmer:
Improved small-set expansion from higher eigenvalues. CoRR abs/1204.4688 (2012) - [i18]Per Austrin, Ryan O'Donnell, John Wright:
A new point of NP-hardness for 2-to-1 Label Cover. CoRR abs/1204.5666 (2012) - [i17]Ryan O'Donnell:
Open Problems in Analysis of Boolean Functions. CoRR abs/1204.6447 (2012) - [i16]Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright:
New NP-hardness results for 3-Coloring and 2-to-1 Label Cover. CoRR abs/1210.5648 (2012) - [i15]Ryan O'Donnell, Yuan Zhou:
Approximability and proof complexity. CoRR abs/1211.1958 (2012) - [i14]Manuel Kauers, Ryan O'Donnell, Li-Yang Tan, Yuan Zhou:
Hypercontractive inequalities via SOS, with an application to Vertex-Cover. CoRR abs/1212.5324 (2012) - 2011
- [j17]Ryan O'Donnell, Rocco A. Servedio:
The Chow Parameters Problem. SIAM J. Comput. 40(1): 165-199 (2011) - [j16]Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer:
Testing Fourier Dimensionality and Sparsity. SIAM J. Comput. 40(4): 1075-1100 (2011) - [c40]Ryan O'Donnell, Yi Wu, Yuan Zhou:
Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups. CCC 2011: 23-33 - [c39]Ryan O'Donnell, John Wright, Yuan Zhou:
The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions. ICALP (1) 2011: 330-341 - [c38]Ryan O'Donnell, Yi Wu, Yuan Zhou:
Optimal lower bounds for locality sensitive hashing (except when q is tiny). ICS 2011: 275-283 - [c37]Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi Wu:
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions. SODA 2011: 1590-1606 - [c36]