Ryan O'Donnell

    
      Associate Professor
      Theory Group, Computer Science Dept., CMU
      7213 Gates Center
      odon...@cs.cmu.edu

      Administrative Assistant: Chase Klingensmith
      Phone: (412) 268-3041
      Email: ch...sek@cs.cmu.edu

My book

  Analysis of Boolean Functions

Most recent teaching

      15-859T: A Theorist's Toolkit
 

Research publications

    

Other writings

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

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

Algorithmic signaling of features in auction design
S. Dughmi, N. Immorlica, R. O'Donnell, L.-Y. Tan.
      Manuscript

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

Improved NP-inapproximability for 2-variable linear equations
J. Håstad, S. Huang, R. Manokaran, R. O'Donnell, J. Wright.
      Manuscript

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

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.
      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, J. Wright, L.-Y. Tan.
      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, R. O'Donnell.
      CCC '12
      An expanded version, with N. Kirshner also as coauthor, will appear.

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

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

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).
      For complete correct statements, please see my book.

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

Some of my talks

Testing surface area (pps)
      Bertinoro, 2014.

Approximability and proof complexity (pps)
      ELC Tokyo, 2013.

Approximability and sums of squares (pps)
      Purdue, 2012.

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

Fall 2012:       15-859S / 21-801A: Analysis of Boolean Functions
Spring '12-'13: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 (lecture notes to return, eventually)
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
         Yuan Zhou (joint with Venkat Guruswami)
     Current:
         Sarah R. Allen
         David Witmer (joint with Anupam Gupta)
         John Wright

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

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