bio | website | cs.cmu.edu/~odonnell |
---|---|---|
location | ||
age | ||
visits | member for | 5 years, 3 months |
seen | 20 hours ago | |
stats | profile views | 1,045 |
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 |
Jul 2 |
awarded | Curious |
Jun 4 |
awarded | Revival |
Jan 13 |
awarded | Nice Question |
Jan 3 |
comment |
Computation complexity of calculating the cdf of an n-th dimensional gaussian random vector
essentially needs to know a point inside the convex set to "get started". Since your set is an explicitly given intersection of n halfspaces, it should be straightforward to explicitly obtain such a point. In other words, I feel that it should be possible to work around the requirement and apply the Cousins-Vempala paper to your setting. |
Jan 3 |
comment |
Computation complexity of calculating the cdf of an n-th dimensional gaussian random vector
Ah, good question. Okay, it occurs to me now that for relative accuracy $\epsilon$ you should be able to do it in time $\mathrm{poly}(n/\epsilon)$ using this paper of Cousins and Vempala (or those that it cites): arxiv.org/abs/1306.5829 It gives such an approximation for the Gaussian volume of any convex set, in fact. A small catch is that it requires some technical condition like the set containing the unit ball. However, from what I know of this subject, that is not a very strict requirement. It's more like a simple example of a possible requirement; really, the algorithm just |
Jan 3 |
answered | Computation complexity of calculating the cdf of an n-th dimensional gaussian random vector |
Nov 27 |
awarded | Citizen Patrol |
Nov 13 |
answered | Cardinality of intersection of a random subset with a fixed subset |