3,132 reputation
1430
bio website cs.cmu.edu/~odonnell
location
age
visits member for 5 years, 9 months
seen 9 hours ago

2d
comment An inequality for the ratio of standard Young tableau with {1,2,…,k} in the first row
I think Suvrit means this question: mathoverflow.net/q/65194/658
Aug
1
revised almost diagonal Positive semidefinite Matrix
deleted 68 characters in body
Jul
31
answered almost diagonal Positive semidefinite Matrix
Jul
25
awarded  Necromancer
Jul
25
answered Majorization and Schur Polynomials
May
15
answered About adding a negative definite rank-1 matrix to a symmetric matrix
May
12
comment Expected number of vertices of a hypercube slice — is this new/interesting?
Maybe check out the following papers; from a quick glance they seem like they might be relevant: ......... cs.columbia.edu/~rocco/Public/chow-journal3b.pdf .........and.......... [Goldberg '06]: "A Bound on the Precision Required to Estimate a Boolean Perceptron from its Average Satisfying Assignment"
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