A polynomial number of random points does not determine the volume of a convex body (Q542396)

The author gives a negative answer to the question of existence of a volume computing algorithm using a random point oracle in case of high-dimensional convex body. It is shown that a polynomial number of points does not contain enough information to estimate the volume, regardless of the number of calculations. The main result from this paper is in the following Theorem: ``There do not exist constants \(C,p,k>0\) such that for any dimension \(n\), there exists an algorithm with complexity \(O(n^{k})\) which is correct in estimating the volume of convex bodies in \(\mathbb{R}^{n}\) up to \(C\) with probability \(p\)''.