Fetching the paper…
Reading the bibliography…
We present an $O^*(n^3)$ randomized algorithm for estimating the volume of a well-rounded convex body given by a membership oracle, improving on the previous best complexity of $O^*(n^4)$.
On extensions of the brunn-minkowski and prekopa-liendler theorems, including inequalities for log-concave functions, and with application to the diffusion equationslogarithmic concave measures and functions
H. J. Brascamp and E. H. Lieb · 1976
Earlier work this paper cites.
Computing the volume is difficult
Z. Furedi and I. Barany · 1986
Earlier work this paper cites.
Logarithmically concave functions and sections of convex sets in rn
K. M. Ball · 1988
Earlier work this paper cites.
On the complexity of computing the volume of a polyhedron
M. E. Dyer and A. M. Frieze · 1988
Earlier work this paper cites.
Approximation of the sphere by polytopes having few vertices
Z. Furedi and I. Barany · 1988
Earlier work this paper cites.
A random polynomial time algorithm for approximating the volume of convex bodies
M. E. Dyer, A. M. Frieze, and R. Kannan · 1989
Earlier work this paper cites.
Mixing rate of Markov chains, an isoperimetric inequality, and computing the volume
L. Lovász and M. Simonovits · 1990
Earlier work this paper cites.
Sampling and integration of near log-concave functions
D. Applegate and R. Kannan · 1991
Earlier work this paper cites.
Computing the volume of a convex body: a case where randomness provably helps
M. E. Dyer and A. M. Frieze · 1991
Earlier work this paper cites.
A random polynomial-time algorithm for approximating the volume of convex bodies
M. E. Dyer, A. M. Frieze, and R. Kannan · 1991
Cited alongside, same era.
Random walks in a convex body and an improved volume algorithm
L. Lovász and M. Simonovits · 1993
Cited alongside, same era.
Isoperimetric problems for convex bodies and a localization lemama
R. Kannan, L. Lovász, and M. Simonovits · 1995
Cited alongside, same era.
Random walks and an O ∗ ( n 5 ) O^{*}(n^{5}) volume algorithm for convex bodies
R. Kannan, L. Lovász, and M. Simonovits · 1997
Cited alongside, same era.
An elementary analysis of a procedure for sampling points in a convex body
R. Bubley, M. Dyer, and M. Jerrum · 1998
Cited alongside, same era.
Fast algorithms for logconcave functions: sampling, rounding, integration and optimization
L. Lovász and S. Vempala · 2006
The geometry of logconcave functions and sampling algorithms
L. Lovász and S. Vempala · 2007
Later among the works it cites.
Concentration in a thin euclidean shell for log-concave measures
B. Fleury · 2010
Later among the works it cites.
Approximately gaussian marginals and the hyperplane conjecture
R. Eldan and B. Klartag · 2011
Later among the works it cites.
Volume computation of convex bodies
B. Cousins and S. Vempala · 2013
Later among the works it cites.
Thin shell implies spectral gap up to polylog via a stochastic localization scheme
R. Eldan · 2013
Later among the works it cites.
A cubic algorithm for computing Gaussian volume
B. Cousins and S. Vempala · 2014
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Hit-and-run from a corner
L. Lovász and S. Vempala · 2006
Cited alongside, same era.
Simulated annealing in convex bodies and an O ∗ ( n 4 ) O^{*}(n^{4}) volume algorithm
L. Lovász and S. Vempala · 2006
Cited alongside, same era.
Bypassing KLS: Gaussian cooling and an O ∗ ( n 3 ) O^{*}(n^{3}) volume algorithm
B. Cousins and S. Vempala · 2015
Closest in time.
A practical volume algorithm
B. Cousins and S. Vempala · 2015
Closest in time.