bio  website  cs.cmu.edu/~odonnell 

location  
age  
visits  member for  5 years, 2 months 
seen  19 hours ago  
stats  profile views  1,039 
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 
lowerbound 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 
lowerbound 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 nth 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 CousinsVempala paper to your setting. 
Jan 3 
comment 
Computation complexity of calculating the cdf of an nth 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 nth 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 