Testing Fourier dimensionality and sparsity
P. Gopalan, R.
O'Donnell, R. Servedio,
A. Shpilka, K. Wimmer.
Submitted
Collisions lead to shallower decision trees (pdf)
J. Aspnes, M. Demirbas,
R. O'Donnell, A.
Rudra, S. Uurtamo.
Submitted
3-Bit Dictator testing: 1 vs. 5/8 (pdf, U of T slides)
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, STOC slides)
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, ICMS slides)
U. Feige, G. Kindler,
R. O'Donnell.
Complexity '07
Testing halfspaces (pdf, BIRS slides)
K. Matulef, R.
O'Donnell, R. Rubinfeld, R. Servedio.
SODA '09
SDP gaps and UGC-hardness for Max-Cut-Gain (pdf, Berkeley slides, UT Austin slides)
S. Khot, R.
O'Donnell.
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, LATIN slides)
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
10 page FOCS '05 version: pdf (NW Theory Day slides, CMU slides)
Every decision tree has an influential variable (pdf, UW slides)
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, MIT
slides)
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.
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
|
|
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
Ph.D. students:
Eric Blais
Karl Wimmer
Yi Wu
Editor:
Theory of
Computing journal.
Program Committee member:
Complexity
2009 (Paris)
ICALP
2008 (Reykjavík)
STOC 2007 (San
Diego)
Complexity
2005 (San Jose)
STOC 2005
(Baltimore)
My CV (pdf)
A crossword
D. Liben-Nowell, R.
O'Donnell.
New York Times, August 3, 2005.
Another crossword
D. Liben-Nowell, R.
O'Donnell.
New York Times, March 25, 2004.
|