bio | website | cs.cmu.edu/~odonnell |
---|---|---|
location | ||
age | ||
visits | member for | 5 years, 10 months |
seen | 16 hours ago | |
stats | profile views | 1,141 |
Aug
12 |
answered | Measures on Young tableaux |
Aug
2 |
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$? |