Ryan O'Donnell

Books

  Analysis of Boolean Functions
     (serialization in progress, follow on Twitter)

Computational applications of noise sensitivity (PhD thesis, pdf)

Research publications

Some of my talks

A new point of NP-hardness for 2-to-1 Label Cover
P. Austrin, R. O'Donnell, J. Wright.
      Manuscript

Improved small-set expansion from higher eigenvalues (pdf)
R. O'Donnell, D. Witmer.
      Manuscript

Gaussian noise sensitivity and Fourier tails (pdf)
G. Kindler, R. O'Donnell.
      CCC '12

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

Linear programming, width-1 CSPs, and robust satisfaction (pdf)
G. Kun, R. O'Donnell, S. Tamaki, Y. Yoshida, Y. Zhou.
      ITCS '12

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.
      Manuscript

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.
      ITCS '11

A new proof of the density Hales-Jewett theorem (pdf)
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.
      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 and rounding in high dimensions (pdf)
G. Kindler, R. O'Donnell, A. Rao, A. Wigderson.
      FOCS '08

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

Some topics in analysis of boolean functions (pdf)
R. O'Donnell.
      Article accompanying STOC '08 tutorial

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.
      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

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

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

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

Approximability of CSPs (pdf)
      Fields Institute, notes and exercises for two summer school lectures, 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.

Teaching

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 '07-'09:    15-359: Probability and Computing
Spring 2009:   15-855: Intensive Intro to Complexity
Spring 2008:   15-854B: Advanced Approximation Algorithms
Spring 2007:   15-859S: Analysis of Boolean Functions
Autumn 2005: CSE 533: The PCP Theorem and Hardness of Approximation
                              (University of Washington)

More

Ph.D. students
     Graduated:
         Karl Wimmer
         Yi Wu
         Eric Blais
     Current:
         David Witmer (joint with Anupam Gupta)
         John Wright
         Yuan Zhou (joint with Venkat Guruswami)

Editor:
     Theory of Computing (ToC)
     SIAM Journal on Discrete Mathematics (SIDMA)
     Electronic Colloquium on Computational Complexity (ECCC)

Program Committee member:
     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
Photo of Ryan O'Donnell