2,718 reputation
1127
bio website cs.cmu.edu/~odonnell
location
age
visits member for 4 years, 10 months
seen 8 hours ago

18h
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
Oct
22
accepted What are good English-language sources for reading about the Luzin affair?
Oct
19
awarded  Informed
Oct
19
comment Convergence of orthogonal polynomial expansions
Oh, I guess the desired uniform convergence statement from in #1 probably follows from Egorov's theorem.
Oct
19
answered Convergence of orthogonal polynomial expansions
Oct
18
awarded  Yearling
Oct
14
asked What are good English-language sources for reading about the Luzin affair?
Oct
8
awarded  Constituent
Oct
3
awarded  Quorum
Oct
3
awarded  Caucus