Ryan O'Donnell
where else to find them
no profile links on file
what they talk about
where they keep going back
no series more than once — all 5 in the filters
on a stage with
all 4 in the filters
who talks about the same things
nobody close enough yet
| title | conference | date |
|---|---|---|
| Explicit Orthogonal and Unitary Designs | Beyond the Boolean Cube 2023 | 2023-06-26 |
Gives a strongly explicit construction of ε‑approximate k‑designs for O(N) and U(N) with N = 2^n, achieving size poly(N^k/ε) (equivalently seed length O(nk +… | ||
| Explicit Abelian Lifts and Quantum LDPC Codes | ITCS 2022 | 2022-01-31 |
Constructs polynomial-time explicit d-regular expanders that are Z_L lifts (and more generally transitive abelian lifts) for L up to about 2^{cN}… | ||
| Optimizing Noncommutative Polynomials: The SYK Model | Rigorous Evidence for Information-Computation Trade-offs | 2021-09-13 |
Random SYK Hamiltonians (Gaussian coefficients normalized so E[sum A_S^2]=1) live as implicit 2^{N/2}-dimensional Majorana matrices and have OPT(H) = Θ(√N)… | ||
| SOS and the Dreaded Bit-complexity | Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017) | 2017-11-06 |
Claims that degree-D Sum-of-Squares proofs are computable in n^{O(D)} time are misleading: semidefinite feasibility suffers big-R / little-r bit-size issues… | ||
| Sum of Squares Lower Bounds for Refuting Any CSP | Structure vs. Randomness 2017 | 2017-04-10 |
Proves tight lower bounds showing the Sum‑of‑Squares (SOS) hierarchy cannot refute random CSPs below the specific density thresholds it earlier achieves… | ||
| nothing matches | ||