bio | website | cs.cmu.edu/~odonnell |
---|---|---|
location | ||
age | ||
visits | member for | 5 years, 7 months |
seen | 11 hours ago | |
stats | profile views | 1,092 |
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 |
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$ |