Ryan O'Donnell

Affiliations:
  • Carnegie Mellon University, Pittsburgh, USA


According to our database1, Ryan O'Donnell authored at least 125 papers between 2002 and 2023.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Quantum chi-squared tomography and mutual information testing.
CoRR, 2023

Mean estimation when you have the source code; or, quantum Monte Carlo methods.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Explicit orthogonal and unitary designs.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Query-optimal estimation of unitary channels in diamond distance.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022
Explicit Near-Ramanujan Graphs of Every Degree.
SIAM J. Comput., June, 2022

Fooling Polytopes.
J. ACM, 2022

Optimizing strongly interacting fermionic Hamiltonians.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

The Quantum Union Bound made easy.
Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

Explicit Abelian Lifts and Quantum LDPC Codes.
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

The SDP Value of Random 2CSPs.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Toward Instance-Optimal State Certification With Incoherent Measurements.
Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

High-Dimensional Expanders from Chevalley Groups.
Proceedings of the 37th Computational Complexity Conference, 2022

2021
Sherali-Adams Strikes Back.
Theory Comput., 2021

Pauli error estimation via Population Recovery.
Quantum, 2021

Analysis of Boolean Functions.
CoRR, 2021

Fooling Gaussian PTFs via Local Hyperconcentration.
CoRR, 2021

Fiber bundle codes: breaking the <i>n</i><sup>1/2</sup> polylog(<i>n</i>) barrier for Quantum LDPC codes.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Improved Quantum data analysis.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Quantum Approximate Counting with Nonadaptive Grover Iterations.
Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Learning sparse mixtures of permutations from noisy information.
Proceedings of the Conference on Learning Theory, 2021

2020
Editorial from the New Editor-in-Chief.
ACM Trans. Comput. Theory, 2020

Sharp Bounds for Population Recovery.
Theory Comput., 2020

Fiber Bundle Codes: Breaking the N<sup>1/2</sup> polylog(N) Barrier for Quantum LDPC Codes.
CoRR, 2020

Fooling Gaussian PTFs via local hyperconcentration.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

The SDP Value for Random Two-Eigenvalue CSPs.
Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

<i>X</i>-Ramanujan graphs.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Lower Bounds for Testing Complete Positivity and Quantum Separability.
Proceedings of the LATIN 2020: Theoretical Informatics, 2020

Explicit near-fully X-Ramanujan graphs.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019
X-Ramanujan Graphs.
CoRR, 2019

Quantum state certification.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

The threshold for SDP-refutation of random regular NAE-3SAT.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

SOS Lower Bounds with Hard Constraints: Think Global, Act Local.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

A Log-Sobolev Inequality for the Multislice, with Applications.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018
Special Issue: CCC 2017: Guest Editor's Foreword.
Theory Comput., 2018

Learning sparse mixtures of rankings from noisy information.
CoRR, 2018

On Closeness to k-Wise Uniformity.
Proceedings of the Approximation, 2018

2017
Improved NP-Inapproximability for 2-Variable Linear Equations.
Theory Comput., 2017

Guest Column: A Primer on the Statistics of Longest Increasing Subsequences and Quantum States (Shortened Version).
SIGACT News, 2017

Efficient quantum tomography II.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Sum of squares lower bounds for refuting any CSP.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Optimal mean-based algorithms for trace reconstruction.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Quantum Automata Cannot Detect Biased Coins, Even in the Limit.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016
The weakness of CTC qubits and the power of approximate counting.
Electron. Colloquium Comput. Complex., 2016

SOS is not obviously automatizable, even approximately.
Electron. Colloquium Comput. Complex., 2016

Bounding laconic proof systems by solving CSPs in parallel.
Electron. Colloquium Comput. Complex., 2016

Efficient quantum tomography.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Polynomial Bounds for Decoupling, with Applications.
Proceedings of the 31st Conference on Computational Complexity, 2016

2015
Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups.
ACM Trans. Comput. Theory, 2015

Beating the random assignment on constraint satisfaction problems of bounded degree.
Electron. Colloquium Comput. Complex., 2015

Continuous analogues of the Most Informative Function problem.
CoRR, 2015

Quantum Spectrum Testing.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Algorithmic Signaling of Features in Auction Design.
Proceedings of the Algorithmic Game Theory - 8th International Symposium, 2015

Optimal Bounds for Estimating Entropy with PMF Queries.
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Conditioning and covariance on caterpillars.
Proceedings of the 2015 IEEE Information Theory Workshop, 2015

How to Refute a Random CSP.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover.
ACM Trans. Comput. Theory, 2014

Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010).
SIAM J. Comput., 2014

One time-travelling bit is as good as logarithmically many.
Electron. Colloquium Comput. Complex., 2014

Social choice, computational complexity, Gaussian geometry, and Boolean functions.
CoRR, 2014

Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Testing Surface Area.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Hypercontractive inequalities via SOS, and the Frankl-Rödl graph.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

One Time-traveling Bit is as Good as Logarithmically Many.
Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

A Composition Theorem for Parity Kill Number.
Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

Goldreich's PRG: Evidence for Near-Optimal Polynomial Stretch.
Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

Analysis of Boolean Functions.
Cambridge University Press, ISBN: 978-1-10-703832-5, 2014

2013
Special Issue on Analysis of Boolean Functions: Guest Editors' Foreword.
Theory Comput., 2013

KKL, Kruskal-Katona, and Monotone Nets.
SIAM J. Comput., 2013

Approximability and proof complexity.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

A Composition Theorem for the Fourier Entropy-Influence Conjecture.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Learning Sums of Independent Integer Random Variables.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
Pareto Optimal Solutions for Smoothed Analysts.
SIAM J. Comput., 2012

Hypercontractive inequalities via SOS, with an application to Vertex-Cover
CoRR, 2012

Open Problems in Analysis of Boolean Functions
CoRR, 2012

Improved small-set expansion from higher eigenvalues
CoRR, 2012

Spherical cubes: optimal foams from computational hardness amplification.
Commun. ACM, 2012

A new point of NP-hardness for unique games.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Linear programming, width-1 CSPs, and robust satisfaction.
Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Gaussian Noise Sensitivity and Fourier Tails.
Proceedings of the 27th Conference on Computational Complexity, 2012

A New Point of NP-Hardness for 2-to-1 Label Cover.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
The Chow Parameters Problem.
SIAM J. Comput., 2011

Testing Fourier Dimensionality and Sparsity.
SIAM J. Comput., 2011

Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010
Polynomial regression under arbitrary product distributions.
Mach. Learn., 2010

Fooling functions of halfspaces under product distributions.
Electron. Colloquium Comput. Complex., 2010

New degree bounds for polynomial threshold functions.
Comb., 2010

Testing (Subclasses of) Halfspaces.
Proceedings of the Property Testing - Current Research and Surveys, 2010

SDP Gaps for 2-to-1 and Other Label-Cover Variants.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Lower Bounds for Testing Function Isomorphism.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

k<sup> + </sup> Decision Trees - (Extended Abstract).
Proceedings of the Algorithms for Sensor Systems, 2010

2009
SDP Gaps and UGC-hardness for Max-Cut-Gain.
Theory Comput., 2009

Optimal lower bounds for locality sensitive hashing (except when q is tiny).
Electron. Colloquium Comput. Complex., 2009

Conditional hardness for satisfiable 3-CSPs.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

3-bit dictator testing: 1 vs. 5/8.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Testing ±1-weight halfspace.
Proceedings of the Approximation, 2009

2008
Learning Mixtures of Product Distributions over Discrete Domains.
SIAM J. Comput., 2008

Extremal properties of polynomial threshold functions.
J. Comput. Syst. Sci., 2008

Some Topics in Analysis of Boolean Functions.
Electron. Colloquium Comput. Complex., 2008

Eliminating Cycles in the Discrete Torus.
Algorithmica, 2008

An optimal sdp algorithm for max-cut, and equally optimal long code tests.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Learning Geometric Concepts via Gaussian Surface Area.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Spherical Cubes and Rounding in High Dimensions.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
Learning Monotone Decision Trees in Polynomial Time.
SIAM J. Comput., 2007

Testing Halfspaces.
Electron. Colloquium Comput. Complex., 2007

Understanding Parallel Repetition Requires Understanding Foams.
Electron. Colloquium Comput. Complex., 2007

Approximation by DNF: Examples and Counterexamples.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006
PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption
CoRR, 2006

On the fourier tails of bounded functions over the discrete cube.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

SDP gaps and UGC-hardness for MAXCUTGAIN.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption.
Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

2005
Coin flipping from a cosmic source: On error correction of truly random bits.
Random Struct. Algorithms, 2005

Learning DNF from random walks.
J. Comput. Syst. Sci., 2005

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?
Electron. Colloquium Comput. Complex., 2005

Noise stability of functions with low influences: invariance and optimality
CoRR, 2005

Every decision tree has an influential variable
CoRR, 2005

Every decision tree has an in.uential variable.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Noise stability of functions with low in.uences invariance and optimality.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004
Hardness amplification within <sub>NP</sub>.
J. Comput. Syst. Sci., 2004

Learning functions of k relevant variables.
J. Comput. Syst. Sci., 2004

Learning intersections and thresholds of halfspaces.
J. Comput. Syst. Sci., 2004

2003
On the noise sensitivity of monotone functions.
Random Struct. Algorithms, 2003

Learning juntas.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002
Hardness amplification within NP.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Derandomized dimensionality reduction with applications.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002


  Loading...