The recently published April 2026 issue of the Journal of the ACM contains a paper by Jia, Laddha, Lee, and Vempala (Jia et al. 2026) that gives a faster algorithm for the central problem of computing the volume of a convex body.
One of the fundamental algorithmic problems in geometry is to compute the volume of a convex body . In the oracle model considered here, the input is given by a membership oracle: for every point with rational coordinates, the oracle answers whether . The complexity of an algorithm is measured by the number of oracle queries it makes. Exact volume computation is -hard, even when is a polytope (Dyer and Frieze 1988). Moreover, Bárány and Füredi proved in 1987 that if and are the upper and lower bounds on produced by any deterministic polynomial-time algorithm, then there are convex bodies for which for some constant (Bárány and Füredi 1987). Thus, in the deterministic polynomial-time setting, the worst-case approximation guarantee deteriorates faster than exponentially with the dimension.
In 1991, however, Dyer, Frieze, and Kannan developed a randomized algorithm that approximates the volume of any convex body to relative error , with success probability at least , using a number of oracle queries polynomial in , , and (Dyer et al. 1991). This was a major theoretical breakthrough, although the original running time, , was far from practical; here suppresses logarithmic factors and the dependence on and . Subsequent work steadily reduced the exponent. In 2006, Lovász and Vempala improved the bound to , or when the dependence on the accuracy parameter is made explicit (Lovász and Vempala 2006). In 2018, Cousins and Vempala obtained an algorithm that is faster in many cases (Cousins and Vempala 2018). More precisely, for every , , and convex body that contains the unit ball, their algorithm returns, with probability at least , an estimate of within relative error using oracle queries, where and is uniformly distributed on .
A convex body is called well-rounded when . For this important class of bodies, the Cousins–Vempala bound becomes .
The new work of Jia, Laddha, Lee, and Vempala extends this level of performance to general convex bodies in the high-accuracy regime. Their algorithm has complexity When is sufficiently small, the term dominates, matching the complexity previously available only for well-rounded bodies. For constant , the bound becomes , improving the best earlier general-purpose bound by a factor of .