|
Cubical tilings with sphere-like surface area
G. Kindler,
A. Rao, R. O'Donnell,
A. Wigderson.
Manuscript
Some topics in analysis of boolean functions
R. O'Donnell.
Manuscript
Polynomial regression under arbitrary product distributions
E. Blais, R. O'Donnell,
K. Wimmer.
COLT '08
3-Bit Long Code testing
R. O'Donnell, Y. Wu.
In preparation
Learning geometric concepts via Gaussian surface area
A. Klivans, R.
O'Donnell, R.
Servedio.
Manuscript
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. Rubinfeld, R. O'Donnell, S. Servedio.
To appear
SDP gaps and UGC-hardness for MaxCutGain (ps, pdf)
S. Khot, R.
O'Donnell.
FOCS '06
PAC learning mixtures of Gaussians with no separation assumption (ps, pdf)
J. Feldman,
R. O'Donnell, R.
Servedio.
COLT '06
Eliminating cycles in the discrete torus (ps, pdf)
B. Bollobás, G. Kindler, I. Leader, R.
O'Donnell.
To appear in Algorithmica
Conference version: LATIN '06
On the Fourier tails of bounded functions over the discrete cube (ps, 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 (ps, pdf)
E. Mossel, R. O'Donnell,
K. Oleszkiewicz.
To appear in Annals of Mathematics
10 page FOCS '05 version: ps, pdf
Every decision tree has an influential variable (ps, pdf)
R. O'Donnell, M.
Saks, O. Schramm, R.
Servedio.
FOCS '05
Learning monotone decision trees in polynomial time (ps, 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? (ps, 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 (ps, 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 (ps, pdf)
J. Feldman,
R. O'Donnell, R.
Servedio.
To appear in SIAM Journal of Computing
Conference version: FOCS '05
My 2003 MIT PhD thesis: Computational applications of noise
sensitivity
(ps, pdf)
Learning DNF from random walks (ps, 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 (ps, 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 (ps, pdf)
R. O'Donnell, R.
Servedio.
STOC '03
Learning juntas AKA Learning functions of k relevant
variables (ps, 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 (ps, 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 (ps, pdf)
E. Mossel, R.
O'Donnell.
Random Structures & Algorithms 26(4),
pp. 418-436 (2005).
On the noise sensitivity of monotone functions (ps, 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 (ps, 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 (ps, pdf)
L. Engebretsen,
P. Indyk, R.
O'Donnell.
SODA '02
|
|
Editor:
Theory of
Computing journal.
Program Committee member:
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.
|
