Ryan O'Donnell

    

Teaching

      Assistant Professor
      School of Computer Science, CMU
      7213 Gates Center
      my email address

      Administrative Assistant: Charlotte Yano
      Phone: (412) 268-7656
      Fax: (412) 268-5574

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)

 

Research publications

    

Some of my talks

A new proof of the density Hales-Jewett theorem (pdf)
with D.H.J. Polymath.
      Manuscript

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

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.
      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.
      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.
      Complexity '07

Testing halfspaces (pdf)
K. Matulef, R. O'Donnell, R. Rubinfeld, R. Servedio.
      To appear, SIAM Journal of Computing
      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. Bollobás, 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.
      To appear in Annals of Mathematics, 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 of Computing 37(3), pp. 827-844 (2007).
      Conference version: Complexity '06

Optimal inapproximability results for MAX-CUT and other two-variable CSPs? (pdf)
S. Khot, G. Kindler. E. Mossel, R. O'Donnell.
      SIAM Journal of 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 of Computing 37(5), pp. 1536-1564 (2008).
      Conference version: FOCS '05

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

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: Complexity '03

New degree bounds for polynomial threshold functions (pdf)
R. O'Donnell, R. Servedio.
      To appear in Combinatorica
      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).
      His result can also be used in place of our Theorem 13.
      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 Birkhäuser, 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 / Complexity '02

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

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.

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 aspects of noise sensitivity (pps)
      MIT, 2003.

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

Learning juntas (pps)
      Unknown provenance, 2003. I think Rocco Servedio made/gave this talk, actually.

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

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





More

Ph.D. students
     Graduated:
         Karl Wimmer
     Current:
         Eric Blais
         Ali Kemal Sinop (joint with Venkat Guruswami)
         Yi Wu
         Yuan Zhou (joint with Venkat Guruswami)

Editor:
     Theory of Computing journal.

Program Committee member:
     COLT 2010 (Haifa)
     Complexity 2009 (Paris)
     ICALP 2008 (Reykjavík)
     STOC 2007 (San Diego)
     Complexity 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