2,977 reputation
1330
bio website cs.cmu.edu/~odonnell
location
age
visits member for 5 years, 6 months
seen 4 hours ago

Apr
28
answered Smallest degree of approximating polynomial
Mar
18
answered Berry-Esseen bound in 2 dimensions for linear combinations
Mar
10
comment Central limit theorem with degenerate covariance matrix
Very doubtful that it's optimal. I'll try to find that reference...
Mar
10
comment Gross's log Sobolev inequality proof with variational calculus?
I second Nate's last comment here.
Mar
9
comment Example of a good Zero Knowledge Proof.
By the way, I recently learned that this example has been attributed to Oded Goldreich: wisdom.weizmann.ac.il/~/oded/poster03.html
Mar
9
comment Central limit theorem with degenerate covariance matrix
Hi Iosif: yes, we needed the non-iid case. Sazonov is the earliest paper I know treating this case, but his error bound has a dependency on the smallest eigenvalue of the covariance matrix. I would not be surprised to find a good theorem handling the non-iid, possibly-degenerate-covariance case out there; I just don't know where to find it. (Regarding the moment conditions, we just assumed finite 4th moments for expedience; it's not hard to weaken this style of proof to 3rd moments, or even Lyapunov-type assumptions.)
Mar
9
answered Gross's log Sobolev inequality proof with variational calculus?
Mar
6
answered Central limit theorem with degenerate covariance matrix
Dec
21
awarded  Nice Answer
Dec
19
comment Why relativization can't solve NP !=P?
Yes, I forever lament (and I think many others do too) that the notation for oracles in complexity theory is very broken and confusing. (Ilya gives the canonical example of this, regarding IP and PSPACE.) As others are saying here, you actually define oracles relative to a machine class (i.e., model of computation), not relative to languages or complexity classes. Let's not even get started on the meaning of relativization with respect to promise problems...
Nov
25
comment lower-bound for $Pr[X\geq EX]$
@fedja: I'm almost certain it's still open. I took a small try at it once. But besides agreeing with the fact (written in Feige's paper) that with enough painful work one could probably push his $c$ up a little bit beyond the $1/13$ (or whatever) he achieves, I had no ideas :)
Nov
25
comment lower-bound for $Pr[X\geq EX]$
I agree the question has issues, but while we're all here, I'm reminded of a beautiful problem of Uri Feige's, which at first glance seems like it cannot possibly be hard. (Warning: it is hard.) Let $X_1, \dots, X_n$ be independent and nonnegative, with $E[X_i] = 1$ for all $i$. Can one prove that $Pr[X_1 + \dots + X_n < n+1] \geq c$ for some universal constant $c > 0$? Can one achieve $c = 1/e$?
Nov
13
awarded  Popular Question
Nov
9
awarded  Notable Question
Oct
18
awarded  Yearling
Oct
14
awarded  Explainer
Oct
14
revised What is the minimal $C_k$, such that every $f\colon \{-1,1\}^n\to \mathbb{R}$ of degree at most $k$ satisfies $\|f\|_2\le C_k\|f\|_1$
altered URL
Oct
14
answered What is the minimal $C_k$, such that every $f\colon \{-1,1\}^n\to \mathbb{R}$ of degree at most $k$ satisfies $\|f\|_2\le C_k\|f\|_1$
Sep
2
awarded  Nice Question
Jul
20
answered Random RSK and Plancherel Measure