 | 2009 |
|---|
| 48 |       | Kevin Matulef,
Ryan O'Donnell,
Ronitt Rubinfeld,
Rocco A. Servedio:
Testing ±1-weight halfspace.
APPROX-RANDOM 2009: 646-657 |
| 47 | | Parikshit Gopalan,
Ryan O'Donnell,
Rocco A. Servedio,
Amir Shpilka,
Karl Wimmer:
Testing Fourier Dimensionality and Sparsity.
ICALP (1) 2009: 500-512 |
| 46 | | Kevin Matulef,
Ryan O'Donnell,
Ronitt Rubinfeld,
Rocco A. Servedio:
Testing halfspaces.
SODA 2009: 256-264 |
| 45 | | Ryan O'Donnell,
Yi Wu:
3-bit dictator testing: 1 vs. 5/8.
SODA 2009: 365-373 |
| 44 | | Ryan O'Donnell,
Yi Wu:
Conditional hardness for satisfiable 3-CSPs.
STOC 2009: 493-502 |
| 2008 |
|---|
| 43 | | Eric Blais,
Ryan O'Donnell,
Karl Wimmer:
Polynomial Regression under Arbitrary Product Distributions.
COLT 2008: 193-204 |
| 42 | | Guy Kindler,
Ryan O'Donnell,
Anup Rao,
Avi Wigderson:
Spherical Cubes and Rounding in High Dimensions.
FOCS 2008: 189-198 |
| 41 | | Adam R. Klivans,
Ryan O'Donnell,
Rocco A. Servedio:
Learning Geometric Concepts via Gaussian Surface Area.
FOCS 2008: 541-550 |
| 40 | | Ryan O'Donnell,
Yi Wu:
An optimal sdp algorithm for max-cut, and equally optimal long code tests.
STOC 2008: 335-344 |
| 39 | | Ryan O'Donnell,
Rocco A. Servedio:
The chow parameters problem.
STOC 2008: 517-526 |
| 38 | | Ryan O'Donnell:
Some topics in analysis of boolean functions.
STOC 2008: 569-578 |
| 37 | | Béla Bollobás,
Guy Kindler,
Imre Leader,
Ryan O'Donnell:
Eliminating Cycles in the Discrete Torus.
Algorithmica 50(4): 446-454 (2008) |
| 36 | | Ryan O'Donnell:
Some Topics in Analysis of Boolean Functions.
Electronic Colloquium on Computational Complexity (ECCC) 15(055): (2008) |
| 35 | | Ryan O'Donnell,
Rocco A. Servedio:
Extremal properties of polynomial threshold functions.
J. Comput. Syst. Sci. 74(3): 298-312 (2008) |
| 34 | | Jon Feldman,
Ryan O'Donnell,
Rocco A. Servedio:
Learning Mixtures of Product Distributions over Discrete Domains.
SIAM J. Comput. 37(5): 1536-1564 (2008) |
| 2007 |
|---|
| 33 | | Ryan O'Donnell,
Karl Wimmer:
Approximation by DNF: Examples and Counterexamples.
ICALP 2007: 195-206 |
| 32 | | Uriel Feige,
Guy Kindler,
Ryan O'Donnell:
Understanding Parallel Repetition Requires Understanding Foams.
IEEE Conference on Computational Complexity 2007: 179-192 |
| 31 | | Uriel Feige,
Guy Kindler,
Ryan O'Donnell:
Understanding Parallel Repetition Requires Understanding Foams.
Electronic Colloquium on Computational Complexity (ECCC) 14(043): (2007) |
| 30 | | Kevin Matulef,
Ryan O'Donnell,
Ronitt Rubinfeld,
Rocco A. Servedio:
Testing Halfspaces.
Electronic Colloquium on Computational Complexity (ECCC) 14(128): (2007) |
| 29 | | Subhash Khot,
Guy Kindler,
Elchanan Mossel,
Ryan O'Donnell:
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?.
SIAM J. Comput. 37(1): 319-357 (2007) |
| 28 | | Ryan O'Donnell,
Rocco A. Servedio:
Learning Monotone Decision Trees in Polynomial Time.
SIAM J. Comput. 37(3): 827-844 (2007) |
| 2006 |
|---|
| 27 | | Jon Feldman,
Rocco A. Servedio,
Ryan O'Donnell:
PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption.
COLT 2006: 20-34 |
| 26 | | Subhash Khot,
Ryan O'Donnell:
SDP gaps and UGC-hardness for MAXCUTGAIN.
FOCS 2006: 217-226 |
| 25 | | Ryan O'Donnell,
Rocco A. Servedio:
Learning Monotone Decision Trees in Polynomial Time.
IEEE Conference on Computational Complexity 2006: 213-225 |
| 24 | | Béla Bollobás,
Guy Kindler,
Imre Leader,
Ryan O'Donnell:
Eliminating Cycles in the Discrete Torus.
LATIN 2006: 202-210 |
| 23 | | Irit Dinur,
Ehud Friedgut,
Guy Kindler,
Ryan O'Donnell:
On the fourier tails of bounded functions over the discrete cube.
STOC 2006: 437-446 |
| 22 | | Jon Feldman,
Ryan O'Donnell,
Rocco A. Servedio:
PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption
CoRR abs/cs/0609093: (2006) |
| 2005 |
|---|
| 21 | | Elchanan Mossel,
Ryan O'Donnell,
Krzysztof Oleszkiewicz:
Noise stability of functions with low in.uences invariance and optimality.
FOCS 2005: 21-30 |
| 20 | | Ryan O'Donnell,
Michael E. Saks,
Oded Schramm,
Rocco A. Servedio:
Every decision tree has an in.uential variable.
FOCS 2005: 31-39 |
| 19 | | Jon Feldman,
Ryan O'Donnell,
Rocco A. Servedio:
Learning mixtures of product distributions over discrete domains.
FOCS 2005: 501-510 |
| 18 | | Ryan O'Donnell,
Michael E. Saks,
Oded Schramm,
Rocco A. Servedio:
Every decision tree has an influential variable
CoRR abs/cs/0508071: (2005) |
| 17 | | Elchanan Mossel,
Ryan O'Donnell,
Krzysztof Oleszkiewicz:
Noise stability of functions with low influences: invariance and optimality
CoRR abs/math/0503503: (2005) |
| 16 | | Guy Kindler,
Ryan O'Donnell,
Subhash Khot,
Elchanan Mossel:
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?
Electronic Colloquium on Computational Complexity (ECCC)(101): (2005) |
| 15 | | Nader H. Bshouty,
Elchanan Mossel,
Ryan O'Donnell,
Rocco A. Servedio:
Learning DNF from random walks.
J. Comput. Syst. Sci. 71(3): 250-265 (2005) |
| 14 | | Elchanan Mossel,
Ryan O'Donnell:
Coin flipping from a cosmic source: On error correction of truly random bits.
Random Struct. Algorithms 26(4): 418-436 (2005) |
| 2004 |
|---|
| 13 | | Subhash Khot,
Guy Kindler,
Elchanan Mossel,
Ryan O'Donnell:
Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?
FOCS 2004: 146-154 |
| 12 | | Adam R. Klivans,
Ryan O'Donnell,
Rocco A. Servedio:
Learning intersections and thresholds of halfspaces.
J. Comput. Syst. Sci. 68(4): 808-840 (2004) |
| 11 | | Ryan O'Donnell:
Hardness amplification within NP.
J. Comput. Syst. Sci. 69(1): 68-94 (2004) |
| 10 | | Elchanan Mossel,
Ryan O'Donnell,
Rocco A. Servedio:
Learning functions of k relevant variables.
J. Comput. Syst. Sci. 69(3): 421-434 (2004) |
| 2003 |
|---|
| 9 | | Nader H. Bshouty,
Elchanan Mossel,
Ryan O'Donnell,
Rocco A. Servedio:
Learning DNF from Random Walks.
FOCS 2003: 189- |
| 8 | | Ryan O'Donnell,
Rocco A. Servedio:
Extremal properties of polynomial threshold functions.
IEEE Conference on Computational Complexity 2003: 3-12 |
| 7 | | Elchanan Mossel,
Ryan O'Donnell,
Rocco A. Servedio:
Learning juntas.
STOC 2003: 206-212 |
| 6 | | Ryan O'Donnell,
Rocco A. Servedio:
New degree bounds for polynomial threshold functions.
STOC 2003: 325-334 |
| 5 | | Elchanan Mossel,
Ryan O'Donnell:
On the noise sensitivity of monotone functions.
Random Struct. Algorithms 23(3): 333-350 (2003) |
| 2002 |
|---|
| 4 | | Adam Klivans,
Ryan O'Donnell,
Rocco A. Servedio:
Learning Intersections and Thresholds of Halfspaces.
FOCS 2002: 177-186 |
| 3 | | Ryan O'Donnell:
Hardness Amplification within NP.
IEEE Conference on Computational Complexity 2002: 23 |
| 2 | | Lars Engebretsen,
Piotr Indyk,
Ryan O'Donnell:
Derandomized dimensionality reduction with applications.
SODA 2002: 705-712 |
| 1 | | Ryan O'Donnell:
Hardness amplification within NP.
STOC 2002: 751-760 |
