Ryan O'Donnell | DeepAI

DeepAI

Featured Co-authors

Andrea Montanari
73 publications
Jerry Li
55 publications
Yu Zhao
51 publications
Li-Yang Tan
32 publications
Sitan Chen
29 publications
Rocco A. Servedio
27 publications
Yuval Filmus
25 publications
Anindya De
23 publications
Tselil Schramm
22 publications
Xinyu Wu
18 publications
Sidhanth Mohanty
17 publications

∙ 08/16/2022

Mean estimation when you have the source code; or, quantum Monte Carlo methods

Suppose y is a real random variable, and one is given access to “the cod...

Robin Kothari, et al. ∙

∙ 03/07/2022

High-Dimensional Expanders from Chevalley Groups

Let Φ be an irreducible root system (other than G_2) of rank at least 2,...

Ryan O'Donnell, et al. ∙

∙ 12/02/2021

Explicit Abelian Lifts and Quantum LDPC Codes

For an abelian group H acting on the set [ℓ], an (H,ℓ)-lift of a graph G...

Fernando Granha Jeronimo, et al. ∙

∙ 10/20/2021

Optimizing Strongly Interacting Fermionic Hamiltonians

The fundamental problem in much of physics and quantum chemistry is to o...

Matthew B. Hastings, et al. ∙

∙ 08/02/2021

The SDP value of random 2CSPs

We consider a very wide class of models for sparse random Boolean 2CSPs;...

Amulya Musipatla, et al. ∙

∙ 05/21/2021

Analysis of Boolean Functions

The subject of this textbook is the analysis of Boolean functions. Rough...

Ryan O'Donnell, et al. ∙

∙ 03/13/2021

Fooling Gaussian PTFs via Local Hyperconcentration

We give a pseudorandom generator that fools degree-d polynomial threshol...

Ryan O'Donnell, et al. ∙

∙ 02/25/2021

Toward Instance-Optimal State Certification With Incoherent Measurements

We revisit the basic problem of quantum state certification: given copie...

Sitan Chen, et al. ∙

∙ 09/08/2020

Fiber Bundle Codes: Breaking the N^1/2polylog(N) Barrier for Quantum LDPC Codes

We present a quantum LDPC code family that has distance Ω(N^3/5/polylog(...

Matthew B. Hastings, et al. ∙

∙ 09/05/2020

Explicit near-fully X-Ramanujan graphs

Let p(Y_1, …, Y_d, Z_1, …, Z_e) be a self-adjoint noncommutative polynom...

Ryan O'Donnell, et al. ∙

∙ 09/16/2019

Explicit near-Ramanujan graphs of every degree

For every constant d ≥ 3 and ϵ > 0, we give a deterministic poly(n)-time...

Sidhanth Mohanty, et al. ∙

∙ 06/16/2019

The SDP value for random two-eigenvalue CSPs

We precisely determine the SDP value (equivalently, quantum value) of la...

Sidhanth Mohanty, et al. ∙

∙ 04/06/2019

X-Ramanujan Graphs

Let X be an infinite graph of bounded degree; e.g., the Cayley graph of ...

Sidhanth Mohanty, et al. ∙

∙ 12/24/2018

Sherali--Adams Strikes Back

Let G be any n-vertex graph whose random walk matrix has its nontrivial ...

Ryan O'Donnell, et al. ∙

∙ 11/03/2018

Learning sparse mixtures of rankings from noisy information

We study the problem of learning an unknown mixture of k rankings over n...

Anindya De, et al. ∙

∙ 09/10/2018

A log-Sobolev inequality for the multislice, with applications

Let κ∈N_+^ℓ satisfy κ_1 + ... + κ_ℓ = n and let U_κ denote the "multisli...

Yuval Filmus, et al. ∙

∙ 09/04/2018

SOS lower bounds with hard constraints: think global, act local

Many previous Sum-of-Squares (SOS) lower bounds for CSPs had two deficie...

Pravesh Kothari, et al. ∙

∙ 08/13/2018

Fooling Polytopes

We give a pseudorandom generator that fools m-facet polytopes over {0,1}...

Ryan O'Donnell, et al. ∙

∙ 06/10/2018

On closeness to k-wise uniformity

A probability distribution over -1, 1^n is (eps, k)-wise uniform if, rou...

Ryan O'Donnell, et al. ∙

∙ 04/14/2018

The threshold for SDP-refutation of random regular NAE-3SAT

Unlike its cousin 3SAT, the NAE-3SAT (not-all-equal-3SAT) problem has th...

Yash Deshpande, et al. ∙