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 | |
Research publications | Some of my talks |
|
|
A new proof of the density Hales-Jewett theorem (pdf)
k+ decision trees (pdf)
Testing {-1,1}-weight halfspaces (pdf)
KKL, Kruskal-Katona, and monotone nets (pdf)
Conditional hardness for satisfiable 3-CSPs (pdf)
Testing Fourier dimensionality and sparsity (pdf)
3-Bit Dictator testing: 1 vs. 5/8 (pdf)
Spherical cubes and rounding in high dimensions (pdf)
Learning geometric concepts via Gaussian surface area (pdf)
Some topics in analysis of boolean functions (pdf)
Polynomial regression under arbitrary product distributions (pdf)
The Chow Parameters problem (pdf)
An optimal SDP algorithm for Max-Cut, and equally optimal Long Code
tests (pdf)
Approximation by DNF: examples and counterexamples (pdf)
Understanding parallel repetition requires understanding foams
(pdf)
Testing halfspaces (pdf)
SDP gaps and UGC-hardness for Max-Cut-Gain (pdf)
PAC learning mixtures of Gaussians with no separation assumption (pdf)
Eliminating cycles in the discrete torus (pdf)
On the Fourier tails of bounded functions over the discrete cube (pdf)
Noise stability of functions with low influences: invariance and optimality (pdf)
Every decision tree has an influential variable (pdf)
Learning monotone decision trees in polynomial time (pdf)
Optimal inapproximability results for MAX-CUT and other two-variable
CSPs? (pdf)
Non-interactive correlation distillation, inhomogeneous Markov chains,
Learning mixtures of product distributions over discrete domains (pdf)
My 2003 MIT PhD thesis: Computational applications of noise
sensitivity
(pdf)
Learning DNF from random walks (pdf)
Extremal properties of polynomial threshold functions (pdf)
New degree bounds for polynomial threshold functions (pdf)
Learning juntas AKA Learning functions of k relevant
variables (pdf)
Learning intersections and thresholds of halfspaces (pdf)
Coin flipping from a cosmic source: On error correction of truly random bits (pdf)
On the noise sensitivity of monotone functions (pdf)
Hardness amplification within NP (pdf)
Derandomized dimensionality reduction with applications (pdf) |
Testing Fourier dimensionality and sparsity
(pps) ICALP, 2009.
The Density Hales-Jewett Theorem, and open source mathematics
(pps)
KKL, Kruskal-Katona, and monotone nets (pps)
Zwick's Conjecture is implied by most of Khot's
conjectures (pps)
On Per Austrin's PhD thesis (pps)
Inverse theorems for inapproximability
(pps)
Some topics in
analysis of boolean functions
(pps)
3-Query dictator testing (pps)
Understanding parallel repetition requires understanding foams (pps)
If I were a UGC skeptic... (pps)
Testing halfspaces (pps)
Hardness of approximating Max-Cut-Gain (pps)
Constraint satisfaction and Property testing (and voting and double
bubbles) (pps)
Learning under the uniform disribution: Toward DNF (pps)
Eliminating cycles in the discrete torus (pps)
UGC & SDP, or, Are there any more polynomial-time algorithms? (pps)
Stability and chaos in boolean functions (pps)
Decision trees and influences (pps)
Learning mixtures of product distributions (pps)
Hardness of approximating Max-Cut Vol. 2: Two Conjectures (pps)
Learning DNF (pps)
Extremal properties of polynomial threshold functions (pps)
Computational aspects of noise sensitivity (pps)
New degree bounds for polynomials with prescribed signs (pps)
Learning juntas (pps)
Coin flipping from a cosmic source (pps)
Learning intersections and thresholds of halfspaces (pps)
More
Ph.D. students
Editor:
Program Committee member:
A crossword (spoiler)
Another crossword (spoiler) |