Ryan O'Donnell

Analysis of Boolean Functions book

Current Teaching

Research publications

Videos

Explicit two-sided vertex expanders beyond the spectral barrier
J.-T. Hsieh, T.-C. Lin, S. Mohanty, R. O'Donnell, R. Y. Zhang
      Manuscript

Coboundary expansion inside Chevalley coset complex HDXs
R. O'Donnell, N. Singer   *Author order randomized
      Manuscript

Uniformity testing when you have the source code
C. Canonne, R. Kothari, R. O'Donnell
      Manuscript

Learning the closest product state
A. Bakshi, J. Bostanci, W. Kretschmer, Z. Landau, J. Z. Li, A. Liu, R. O'Donnell, E. Tang
      Manuscript

Computability theory of closed timelike curves
S. Aaronson, M. Bavarian, T. Cubitt, S. Grewal, G. Gueltrini, R. O'Donnell, M. Raat
      Manuscript

Pseudorandom permutations from random reversible circuits
W. He, R. O'Donnell
      Manuscript

Quartic quantum speedups for planted inference
Alexander Schmidhuber, R. O'Donnell, R. Kothari, R. Babbush
      Manuscript

Sparsifying suprema of Gaussian processes
A. De, S. Nadimpalli, R. O'Donnell, R. Servedio
      Manuscript

Quantum chi-squared tomography and mutual information testing (pdf)
S. Flammia, R. O'Donnell
      To appear, Quantum
      QIP '24

Explicit orthogonal and unitary designs (pdf)
R. O'Donnell, R. Servedio, P. Paredes   *Author order randomized
      FOCS '23

Query-optimal estimation of unitary channels in diamond distance (pdf)
J. Haah, R. Kothari, R. O'Donnell, E. Tang
      FOCS '23, QIP '24

Mean estimation when you have the source code; or, quantum Monte Carlo methods (pdf)
R. Kothari, R. O'Donnell
      SODA '23, QIP '23

Explicit abelian lifts and quantum LDPC codes (pdf)
F. G. Jeronimo, T. Mittal, R. O'Donnell, P. Paredes, M. Tulsiani.
      ITCS '22

High-dimensional expanders from Chevalley groups (pdf)
R. O'Donnell, K. Pratt   *Author order randomized
      CCC '22

Optimizing strongly interacting fermionic Hamiltonians (pdf)
M. Hastings, R. O'Donnell
      STOC '22, QIP '22

The SDP value of random 2CSPs (pdf)
A. Musipatla, R. O'Donnell, T. Schramm, X. Wu
      ICALP '22

Pauli error estimation via Population Recovery (pdf)
S. Flammia, R. O'Donnell
      Quantum 5, pp. 549 (2021).
      TQC '21

The Quantum Union Bound made easy (pdf)
R. O'Donnell, R. Venkateswaran   *Author order randomized
      SOSA '22

Toward instance-optimal quantum state certification with independent measurements (pdf)
S. Chen, J. Z. Li, R. O'Donnell
      COLT '22, QIP '22

Improved quantum data analysis (pdf)
C. Bădescu, R. O'Donnell
      To appear, TheoretiCS
      STOC '21

Fiber bundle codes: Breaking the N^1/2polylog(N) barrier for quantum LDPC codes (pdf)
J. Haah, M. Hastings, R. O'Donnell
      QIP '21, STOC '21

Quantum approximate counting with nonadaptive Grover iterations (pdf)
R. Venkateswaran, R. O'Donnell  *Author order randomized
      STACS '21

Explicit near-fully X-Ramanujan graphs (pdf)
R. O'Donnell, X. Wu  *Author order randomized
      FOCS '20

Fooling Gaussian PTFs via local hyperconcentration (pdf)
R. O'Donnell, R. Servedio, L.-Y. Tan  *Author order randomized
with an appendix by D. Kane
      STOC '20

Explicit near-Ramanujan graphs of every degree (pdf)
S. Mohanty, R. O'Donnell, P. Paredes
      SIAM Journal on Computing 2021, special section on STOC 2020.
      STOC '20

Lower bounds for testing complete positivity and quantum separability (pdf)
C. Bădescu, R. O'Donnell
      LATIN '20

The SDP value for random two-eigenvalue CSPs (pdf)
S. Mohanty, R. O'Donnell, P. Paredes
      STACS '20

X-Ramanujan graphs (pdf)
S. Mohanty, R. O'Donnell
      SODA '20

Sherali–Adams strikes back (pdf)
R. O'Donnell, T. Schramm
      Theory of Computing 17(9), pp. 1-30 (2021).
      CCC '19

Learning sparse mixtures of rankings from noisy information (pdf)
A. De, R. O'Donnell, R. Servedio.
      COLT '21

A log-Sobolev inequality for the multislice, with applications (pdf)
Y. Filmus, R. O'Donnell, X. Wu
      To appear, Electronic Journal of Probability
      ITCS '19

Fooling polytopes (pdf)
R. O'Donnell, R. Servedio, L.-Y. Tan
      To appear, Journal of the ACM
      STOC '19

The threshold for SDP-refutation of random regular NAE-3SAT (pdf)
Y. Deshpande, A. Montanari, R. O'Donnell, T. Schramm, S. Sen
      SODA '19

SOS lower bounds with hard constraints: think global, act local (pdf)
P. Kothari, R. O'Donnell, T. Schramm.
      ITCS '19

Quantum state certification (pdf)
C. Bădescu, R. O'Donnell, J. Wright.
      QIP '18, STOC '19

On closeness to k-wise uniformity (pdf)
R. O'Donnell, Y. Zhao.
      RANDOM '18

Sharp bounds for population recovery (pdf)
A. De, R. O'Donnell, R. Servedio.
      Theory of Computing 16(6), pp. 1-20 (2020).

Sum of squares lower bounds for refuting any CSP (pdf)
P. Kothari, R. Mori, R. O'Donnell, D. Witmer.
      STOC '17

Optimal mean-based algorithms for trace reconstruction (pdf)
A. De, R. O'Donnell, R. Servedio.
      Annals of Applied Probability 29(2), pp. 851-874 (2019).
      Conference version: STOC '17

Efficient quantum tomography II (pdf)
R. O'Donnell, J. Wright.
      STOC '17

Quantum automata cannot detect biased coins, even in the limit (pdf)
G. Kindler, R. O'Donnell.
      ICALP '17

SOS is not obviously automatizable, even approximately (pdf)
R. O'Donnell.
      ITCS '17

Bounding laconic proof systems by solving CSPs in parallel (pdf)
J. Li, R. O'Donnell.
      SPAA '17

Polynomial bounds for decoupling, with applications (pdf)
R. O'Donnell, Y. Zhao.
      CCC '16

Efficient quantum tomography (pdf)
R. O'Donnell, J. Wright.
      To appear, Journal of the ACM.
      STOC '16, QIP '16

Remarks on the Most Informative Function Conjecture at fixed mean (pdf)
G. Kindler, R. O'Donnell, D. Witmer.
      Manuscript

Beating the random assignment on constraint satisfaction problems of bounded degree (pdf)
B. Barak, A. Moitra, R. O'Donnell, P. Raghavendra, O. Regev, D. Steurer, L. Trevisan, A. Vijayaraghavan, D. Witmer, J. Wright.
      APPROX '15

How to refute a random CSP (pdf)
S. R. Allen, R. O'Donnell, D. Witmer.
      FOCS '15

Optimal bounds for estimating entropy with PMF queries (pdf)
C. Caferov, B. Kaya, R. O'Donnell, A. C. C. Say.
      MFCS '15

The weakness of CTC qubits and the power of approximate counting (pdf)
R. O'Donnell, A. C. C. Say.
      Transactions on Computation Theory 10(2), no. 5 (2018).

Quantum spectrum testing (pdf)
R. O'Donnell, J. Wright.
      To appear, Communications of Mathematical Physics (2021).
      Conference version: STOC '15, QIP '15

One time-traveling bit is as good as logarithmically many (pdf)
R. O'Donnell, A. C. C. Say.
      FSTTCS '14

Conditioning and covariance on caterpillars (pdf)
S. R. Allen, R. O'Donnell.
      ITW '15

Algorithmic signaling of features in auction design (pdf)
S. Dughmi, N. Immorlica, R. O'Donnell, L.-Y. Tan.
      SAGT '15

Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs (pdf)
I. Benjamini, S.-O. Chan, R. O'Donnell, O. Tamuz, L.-Y. Tan.
      Stochastic Processes and their Applications 126(9), pp. 2719-2733 (2016).

Improved NP-inapproximability for 2-variable linear equations (pdf)
J. Håstad, S. Huang, R. Manokaran, R. O'Donnell, J. Wright.
      Theory of Computing 13(19), pp. 1-51 (2017).
      Conference version: APPROX '15

A composition theorem for parity kill number (pdf)
R. O'Donnell, X. Sun, L.-Y. Tan, J. Wright, Y. Zhao.
      CCC '14

Goldreich's PRG: Evidence for near-optimal polynomial stretch (pdf)
R. O'Donnell, D. Witmer.
      CCC '14
Note (Dec. '21): The proof of Theorem III.2 in this paper is wrong.
      Thanks to Andrej Bogdanov and Aayush Jain for pointing this out.

Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs (pdf)
R. O'Donnell, J. Wright, C. Wu, Y. Zhou.
      SODA '14

Testing surface area (pdf)
P. Kothari, A. Nayyeri, R. O'Donnell, C. Wu.
      SODA '14

Learning sums of independent integer random variables (pdf)
C. Daskalakis, I. Diakonikolas, R. O'Donnell, R. SIIRVedio, L.-Y. Tan.
      FOCS '13

A composition theorem for the Fourier Entropy-Influence conjecture (pdf)
R. O'Donnell, L.-Y. Tan.
      ICALP '13

Hypercontractive inequalities via SOS, and the Frankl-Rödl graph (pdf)
M. Kauers, R. O'Donnell, L.-Y. Tan, Y. Zhou.
      Discrete Analysis 2016:4.
      SODA '14

Approximability and proof complexity (pdf)
R. O'Donnell, Y. Zhou.
      SODA '13

Markov chain methods for small-set expansion (pdf)
R. O'Donnell, D. Witmer.
      Manuscript

New NP-hardness results for 3-Coloring and 2-to-1 Label Cover (pdf)
P. Austrin, R. O'Donnell, L.-Y. Tan, J. Wright.
      Transactions on Computation Theory 6(1), pp. 2:1-20 (2014).
      Preliminary version: APPROX '12, A new point of NP-hardness for 2-to-1 Label Cover

Gaussian noise sensitivity and Fourier tails (pdf)
G. Kindler, N. Kirshner, R. O'Donnell.
      Israel Journal of Mathematics 225(1), pp. 71-109 (2018).
      Conference version: CCC '12

A new point of NP-hardness for Unique Games (pdf)
R. O'Donnell, J. Wright.
      To appear, Journal of the ACM.
      STOC '12

Linear programming, width-1 CSPs, and robust satisfaction (pdf)
G. Kun, R. O'Donnell, S. Tamaki, Y. Yoshida, Y. Zhou.
      ITCS '12
Note (Sep. '13): Theorem 4.1 in this paper is false; there is a counterexample.
      Thanks to Víctor Dalmau and Andrei Krokhin for pointing this out.
      Thus we only have that width-1 implies robust LP-decidability, as in Dalmau--Krokhin.

The Fourier Entropy-Influence Conjecture for certain classes of Boolean functions (pdf)
R. O'Donnell, J. Wright, Y. Zhou.
      ICALP '11

Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups (pdf)
R. O'Donnell, Y. Wu, Y. Zhou.
      CCC '11

Sharpness of KKL on Schreier graphs (pdf)
R. O'Donnell, K. Wimmer.
      Electronic Communications in Probability 18(18), pp. 1-12 (2013).

Pareto optimal solutions for smoothed analysts (pdf)
A. Moitra, R. O'Donnell.
      STOC '11

Hardness results for agnostically learning low-degree polynomial threshold functions (pdf)
I. Diakonikolas, R. O'Donnell, R. Servedio, Y. Wu.
      SODA '11

SDP gaps for 2-to-1 and other Label-Cover variants (pdf)
V. Guruswami, S. Khot, R. O'Donnell, P. Popat, M. Tulsiani, Y. Wu.
      ICALP '10

Fooling functions of halfspaces under product distributions (pdf)
P. Gopalan, R. O'Donnell, Y. Wu, D. Zuckerman.
      CCC '10

Lower bounds for testing function isomorphism (pdf)
E. Blais, R. O'Donnell.
      CCC '10

Optimal lower bounds for locality sensitive hashing (except when q is tiny) (pdf)
R. O'Donnell, Y. Wu, Y. Zhou.
      Transactions on Computation Theory 6(1), pp. 5:1-13 (2014).
      ITCS '11

A new proof of the density Hales-Jewett theorem (pdf, draft version)
Joint work with D.H.J. Polymath.
      Annals of Mathematics 175(3), pp. 1283-1327 (2012).

k⁺ decision trees (pdf)
J. Aspnes, E. Blais, M. Demirbas, R. O'Donnell, A. Rudra, S. Uurtamo.
      ALGOSENSORS '10

Testing {-1,1}-weight halfspaces (pdf)
K. Matulef, R. O'Donnell, R. Rubinfeld, R. Servedio.
      RANDOM '09

KKL, Kruskal-Katona, and monotone nets (pdf)
R. O'Donnell, K. Wimmer.
      SIAM Journal on Computing 42(6), pp. 2375-2399 (2013).
      FOCS '09

Conditional hardness for satisfiable 3-CSPs (pdf)
R. O'Donnell, Y. Wu.
      STOC '09

Testing Fourier dimensionality and sparsity (pdf)
P. Gopalan, R. O'Donnell, R. Servedio, A. Shpilka, K. Wimmer.
      SIAM Journal on Computing 40(4), pp. 1075-1100 (2011).
      Conference version: ICALP '09

3-Bit Dictator testing: 1 vs. 5/8 (pdf)
R. O'Donnell, Y. Wu.
      SODA '09

Spherical cubes: optimal foams from computational hardness amplification (pdf)
G. Kindler, R. O'Donnell, A. Rao, A. Wigderson.
      Simplified exposition in Communications of the ACM 55(10), pp. 90-97 (2012).
      (The misordering of the author names in the CACM version is a copyediting error.)
      Conference version: FOCS '08, Spherical cubes and rounding in high dimensions (pdf)

Learning geometric concepts via Gaussian surface area (pdf)
A. Klivans, R. O'Donnell, R. Servedio.
      FOCS '08

Polynomial regression under arbitrary product distributions (pdf)
E. Blais, R. O'Donnell, K. Wimmer.
      Machine Learning 80(2-3), pp. 273-294 (2010).
      Conference version: COLT '08

The Chow Parameters problem (pdf)
R. O'Donnell, R. Servedio.
      SIAM Journal on Computing 40(1), pp. 165-199 (2011).
      Conference version: STOC '08

An optimal SDP algorithm for Max-Cut, and equally optimal Long Code tests (pdf)
R. O'Donnell, Y. Wu.
      STOC '08

Approximation by DNF: examples and counterexamples (pdf)
R. O'Donnell, K. Wimmer.
      ICALP '07

Understanding parallel repetition requires understanding foams (pdf)
U. Feige, G. Kindler, R. O'Donnell.
      CCC '07

Testing halfspaces (pdf)
K. Matulef, R. O'Donnell, R. Rubinfeld, R. Servedio.
      SIAM Journal on Computing 39(5), pp. 2004-2047 (2010).
      Conference version: SODA '09

SDP gaps and UGC-hardness for Max-Cut-Gain (pdf)
S. Khot, R. O'Donnell.
      Theory of Computing 5, pp. 83-117 (2009).
      Conference version: FOCS '06

PAC learning mixtures of Gaussians with no separation assumption (pdf)
J. Feldman, R. O'Donnell, R. Servedio.
      COLT '06

Eliminating cycles in the discrete torus (pdf)
B. Bollobas, G. Kindler, I. Leader, R. O'Donnell.
      Algorithmica 50(4), pp. 446-454 (2008).
      Conference version: LATIN '06

On the Fourier tails of bounded functions over the discrete cube (pdf)
I. Dinur, E. Friedgut, G. Kindler, R. O'Donnell.
      Israel Journal of Mathematics 160(1), pp. 389-412 (2007)
      Conference version: STOC '06

Noise stability of functions with low influences: invariance and optimality (pdf)
E. Mossel, R. O'Donnell, K. Oleszkiewicz.
      Annals of Mathematics 171(1), pp. 295-341 (2010).
      10 page FOCS '05 version: pdf

Every decision tree has an influential variable (pdf)
R. O'Donnell, M. Saks, O. Schramm, R. Servedio.
      FOCS '05

Learning monotone decision trees in polynomial time (pdf)
R. O'Donnell, R. Servedio.
      SIAM Journal on Computing 37(3), pp. 827-844 (2007).
      Conference version: CCC '06

Optimal inapproximability results for MAX-CUT and other two-variable CSPs? (pdf)
S. Khot, G. Kindler. E. Mossel, R. O'Donnell.
      SIAM Journal on Computing 37(1), pp. 319-357 (2007).
      Conference version: FOCS '04 (FOCS 20-Year Test Of Time Award)

Non-interactive correlation distillation, inhomogeneous Markov chains,
        and the reverse Bonami-Beckner inequality (pdf)
E. Mossel, R. O'Donnell, O. Regev, J. Steif, B. Sudakov.
      Israel Journal of Mathematics 154(1), pp. 299-336 (2006).

Learning mixtures of product distributions over discrete domains (pdf)
J. Feldman, R. O'Donnell, R. Servedio.
      SIAM Journal on Computing 37(5), pp. 1536-1564 (2008).
      Conference version: FOCS '05

Learning DNF from random walks (pdf)
N. Bshouty, E. Mossel, R. O'Donnell, R. Servedio.
      Journal of Computer and System Sciences 71(3), pp. 250-265 (2005)
      Conference version: FOCS '03

Extremal properties of polynomial threshold functions (pdf)
R. O'Donnell, R. Servedio.
      Journal of Computer and System Sciences 74(3), pp. 298-312 (2008)
      Conference version: CCC '03 (Best Paper Award)

New degree bounds for polynomial threshold functions (pdf)
R. O'Donnell, R. Servedio.
      Combinatorica 30(3), pp. 327-358 (2010)
      Conference version: STOC '03

Learning juntas AKA Learning functions of k relevant variables (pdf)
E. Mossel, R. O'Donnell, R. Servedio.
      Journal of Computer and System Sciences 69(3), pp. 421-434 (2004)
      Conference version: STOC '03
Note (Aug. '06): Theorem 12 in this paper turns out to be not new.
      T. Siegenthaler proved it in Transactions of Information Theory 30(5) (1984).
      Thanks to Eric Bach and Lisa Hellerstein for pointing this out.

Learning intersections and thresholds of halfspaces (pdf)
A. Klivans, R. O'Donnell, R. Servedio.
      Journal of Computer and System Sciences 68(4), pp. 808-840 (2004)
      Conference version: FOCS '02

Coin flipping from a cosmic source: On error correction of truly random bits (pdf)
E. Mossel, R. O'Donnell.
      Random Structures & Algorithms 26(4), pp. 418-436 (2005).

On the noise sensitivity of monotone functions (pdf)
E. Mossel, R. O'Donnell.
      Random Structures & Algorithms 23(3), pp. 333-350 (2003).
      Conference version:
            Trends in Mathematics: Mathematics and Computer Science II
            B. Chauvin et. al. ed., publ. by Birkhauser, 2002

Hardness amplification within NP (pdf)
R. O'Donnell.
      Journal of Computer and System Sciences, 69(1), pp. 68-94 (2004).
      Conference version: STOC '02 / CCC '02 (CCC Best Student Paper Award)

Derandomized dimensionality reduction with applications (pdf)
L. Engebretsen, P. Indyk, R. O'Donnell.
      SODA '02

Other writings

Learning and testing quantum states via probabilistic combinatorics and representation theory (pdf)
      A survey appearing in the 2021/2022 Current Developments in Mathematics
      A substantial portion of this was cowritten with J. Wright under the title
          A primer on the statistics of longest increasing subsequences and quantum states
      and appeared in SIGACT News

Social choice, computational complexity, Gaussian geometry, and Boolean functions (pdf)
      Contribution to the proceedings of the 2014 ICM

Analysis of Boolean Functions minicourse (pdf)
      Li-Yang Tan's heroic transcription of my 10-lecture series in Barbados, 2012.

Open problems in Analysis of Boolean Functions (pdf)
      Collected at the Simons Symposium, jointly organized with Mossel and Oleszkiewicz, 2012.

Approximability of CSPs (pdf)
      Notes and exercises for two summer school lectures at the Fields Institute, 2011.

Some topics in analysis of boolean functions (pdf)
      Article accompanying my tutorial at STOC '08.
      ERRATUM: The Hypercontractivity Theorem, as I stated it here, is not (known to be) true.
      What I stated is true for p = 2 (which suffices for most applications).
      The most recent word on these issues is due to Eskenazis and Ivanisvili.

Computational applications of noise sensitivity (pdf)
      My MIT PhD thesis, 2003.

Some of my talks

Fiber bundle codes (ppsx)
      UT Austin, 2020.

Quantum learning of quantum data (ppsx)
      MIFODS, 2020.

Explicit near-Ramanujan graphs of every degree (ppsx)
      BIRS, 2019.

X-Ramanujan graphs (ppsx)
      IAS, 2018.

Log-Sobolev inequality on the multislice (ppsx)
      Princeton, 2018.

Fooling polytopes (ppsx)
      Clay Mathematics Institute, 2018.

Distribution testing in the 21½th century (ppsx)
      Workshop on Frontiers in Distribution Testing, FOCS 2017.

Optimal mean-based algorithms for trace reconstruction (ppsx)
      67th Midwest Theory Day, IU Bloomington, 2017.

Sum of squares lower bounds for refuting any CSP (ppsx)
      Simons Institute, 2017.

SOS is not obviously automatizable, even approximately (ppsx)
      ITCS, 2017.

Video tutorial on analysis of Boolean functions: Part 1, Part 2
      St. Petersburg State University Complexity Semester, 2016.

Learning and testing quantum states (ppsx)
      RS&A 2015, Charles River Probability Lectures, 2015.

How to refute a random CSP (ppsx)
      Harvard, 2015.

Quantum spectrum testing (ppsx)
      Columbia, 2015.

Time travel (ppsx)
      Magic 77.

One time-traveling bit is as good as logarithmically many (ppsx)
      FSTTCS, 2014.

Social choice, computational complexity, Gaussian geometry, and Boolean functions (ppsx)
      ICM, 2014. Open with PowerPoint to see my patter in the "notes".

Testing surface area (pps)
      Bertinoro, 2014.

Hypercontractivity and sums of squares
Approximability and proof complexity
Approximability and sums of squares
      (ppsx, pps, pps respectively)
      NUS 2016, ELC Tokyo 2013, Purdue 2012 (respectively).

Linear programming, width-1 CSPs, and robust satisfaction (pps)
      EaGL IV, 2011.

Pareto optimal solutions for smoothed analysts (pps)
      IAS, 2011.

A regularity lemma for low noisy-influences (pps)
      LTF-PTF Workshop, 2010.

Optimal lower bounds for locality sensitive hashing (except when q is tiny) (pps)
      New York Area Theory Day, 2010.

Invariance principles in theoretical computer science (pps)
      Tsinghua, 2010.

Quasirandom boolean functions, and inapproximability (pps)
      IAS, 2010.

Testing Fourier dimensionality and sparsity (pps)
      ICALP, 2009.

The Density Hales-Jewett Theorem, and open source mathematics (pps)
      Microsoft / IAS, 2009.

KKL, Kruskal-Katona, and monotone nets (pps)
      MIT, 2009.

Zwick's Conjecture is implied by most of Khot's conjectures (pps)
      TTI, 2008.

On Per Austrin's PhD thesis (pps)
      KTH, 2008. I was the "opponent".

Inverse theorems for inapproximability (pps)
      MSRI, Nov. 5, 2008. A survey talk for mathematicians.

Some topics in analysis of boolean functions (pps)
      STOC tutorial, 2008. Open with PowerPoint to see my patter in the "notes".

3-Query dictator testing (pps)
      U of T, 2008.

Understanding parallel repetition requires understanding foams (pps)
      ICMS, 2007. Prize offers no longer valid. Enjoy Asteroids.

If I were a UGC skeptic... (pps)
      Oberwolfach, 2007. Half of a 10-minute talk.

Testing halfspaces (pps)
      BIRS, 2006.

Hardness of approximating Max-Cut-Gain (pps)
      Austin, 2006.

SDP integrality gaps and Long Code tests for Max-Cut-Gain (pps)
      FOCS, 2006.

Constraint satisfaction and property testing (and voting and double bubbles) (pps)
      CMU, President's Day 2006.

Learning under the uniform disribution: Toward DNF (pps)
      GA Tech, 2006. A survey.

Eliminating cycles in the discrete torus (pps)
      LATIN, 2006.

UGC & SDP, or, Are there any more polynomial-time algorithms? (pps)
      Berkeley, 2005.

Stability and chaos in boolean functions (pps)
      Northwest Theory Day, 2005.

Decision trees and influences (pps)
      UW, 2005.

Learning mixtures of product distributions (pps)
      Berkeley, 2004.

Hardness of approximating Max-Cut Vol. 2: Two Conjectures (pps)
      Yale, 2004. Second in a two-volume series with Guy Kindler.

Learning DNF (pps)
      A survey talk given... somewhere, 2003. Avrim's $1000 is still available.

Extremal properties of polynomial threshold functions (pps)
      CCC, 2003.

Computational applications of noise sensitivity (pps)
      MIT, 2003.

New degree bounds for polynomials with prescribed signs (pps)
      Unknown venue, 2003.

Coin flipping from a cosmic source (pps)
      IAS, 2003.

Learning intersections and thresholds of halfspaces (pps)
      Microsoft, 2002.

Prior teaching (lecture notes and videos)

Spring 2024:	15-751: CS Theory Toolkit
Fall 2023:	15-459: Undergraduate quantum computing
Spring 2023:	15-750: Algorithms in the Real World
Fall 2022:	15-459: Undergraduate Quantum Computation
Spring 2022:	15-751: CS Theory Toolkit
Fall 2021:	15-459: Undergraduate Quantum Computation
Spring 2021:	15-855: Graduate Computational Complexity Theory
Fall 2019:	15-459: Undergraduate Quantum Computation
Spring 2020:	15-751: CS Theory Toolkit
Fall 2019:	15-455: Undergraduate Complexity Theory
Fall 2018:	15-859BB: Quantum Computation and Quantum Information
Spring 2018:	15-455: Undergraduate Complexity Theory
Fall 2017:	15-855: Graduate Computational Complexity Theory
Spring 2017:	15-455: Undergraduate Complexity Theory
Fall 2016:	15-751: A Theorist's Toolkit
Spring 2016:	15-251: Great Theoretical Ideas in Computer Science
Fall 2015:	15-859BB: Quantum Computation and Information
Spring 2015:	15-251: Great Theoretical Ideas in Computer Science
Fall 2014:	CmpE 587: Introduction to Research in Theoretical Computing (Bogaziçi University)
Fall 2013:	15-859T: A Theorist's Toolkit
Spring 2013:	15-251: Great Theoretical Ideas in Computer Science
Fall 2012:	15-859S / 21-801A: Analysis of Boolean Functions
Spring 2012:	15-251: Great Theoretical Ideas in Computer Science
Fall 2011:	15-859E: Linear Programming and Semidefinite Programming
Spring 2010:	15-859U: Theoretical Computer Science's Greatest Hits, 2009
Fall 2009:	15-359: Probability and Computing
Spring 2009:	15-855: Intensive Intro to Complexity
Fall 2008:	15-359: Probability and Computing
Spring 2008:	15-854B: Advanced Approximation Algorithms
Fall 2007:	15-359: Probability and Computing
Spring 2007:	15-859S: Analysis of Boolean Functions
Autumn 2005:	CSE 533: The PCP Theorem and Hardness of Approximation (University of Washington)

More

Students supervised:
     Past:
         Karl Wimmer (Ph.D. 2009)
         Yi Wu (Ph.D. 2010)
         Eric Blais (Ph.D. 2012)
         Yuan Zhou (Ph.D. 2014, joint with Venkat Guruswami)
         John Wright (Ph.D. 2016)
         Sarah R. Allen (M.Sc. 2016)
         David Witmer (Ph.D. 2017, joint with Anupam Gupta)
         Yongshan Ding (B.S. thesis 2016)
         Chris Jones (B.S. thesis 2016)
         Calvin Beideman (B.S. thesis 2018)
         Yeongwoo Hwang (B.S. thesis 2018, joint with Anıl Ada)
         Sidhanth Mohanty (B.S. thesis 2018)
         Xinyu Wu (M.Sc. 2019)
         Corwin de Boor (M.Sc. 2019)
         Amulya Musipatla (M.Sc. 2021)
         Ramgopal Venkateswaran (B.S. thesis 2021)
         Yu Zhao (Ph.D. 2021)
         Pedro Paredes (Ph.D. 2022)
         Kevin Pratt (Ph.D. 2023)
     Present Ph.D. students:
         Costin Bădescu
         William He
         Jingxun Liang
         Noah Singer
         Xinyu Wu

Professional:
     Member, Simons Institute Scientific Advisory Board
     Board, Electronic Colloquium on Computational Complexity (ECCC)
     Formerly:
        Editor-in-Chief, ACM Transactions on Computation Theory
        Member, SLMath (MSRI) Scientific Advisory Committee
        Board of trustees, Computational Complexity Foundation
        Editor, SIAM Journal on Discrete Mathematics
        Member, Committee for the Advancement of TCS

Program Committee member:
     STOC 2024, chair (Vancouver)
     FOCS 2023 (Santa Cruz)
     SOSA 2023 (Florence)
     CCC 2021 (Toronto)
     STOC 2021 (Rome)
     RANDOM 2020 (Seattle)
     FOCS 2018 (Paris)
     CCC 2017, chair (Riga)
     RANDOM 2016 (Paris)
     ICML 2016 (New York)
     ITCS 2015 (Rehovot)
     CCC 2013 (Palo Alto)
     RANDOM 2012 (Boston)
     SODA 2012 (Kyoto)
     FOCS 2010 (Las Vegas)
     COLT 2010 (Haifa)
     CCC 2009 (Paris)
     ICALP 2008 (Reykjavik)
     STOC 2007 (San Diego)
     CCC 2005 (San Jose)
     STOC 2005 (Baltimore)

A crossword (spoiler)
D. Liben-Nowell, R. O'Donnell.
      New York Times, August 3, 2005.

Another crossword (spoiler)
D. Liben-Nowell, R. O'Donnell.
      New York Times, March 25, 2004.

My CV
Picture of Ryan O'Donnell