2,823 reputation
1329
bio website cs.cmu.edu/~odonnell
location
age
visits member for 5 years, 2 months
seen 19 hours ago

2d
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
Oct
26
awarded  Enthusiast