Approximating the volume of definable sets
Pascal Koiran · 2002
The first part of this paper deals with finite-precision arithmetic. We give an upper bound on the precision that should be used in a Monte-Carlo integration method. Such bounds have been known only for convex sets; our bound applies to almost any "reasonable" set. In the second part of the paper, we show how to construct in polynomial time first-order formulas that approximately define the volume of definable sets. This result is based on a VC dimension hypothesis, and is inspired from the well-known complexity-theoretic result "BPP/spl sube//sub 2/". Finally, we show how these results can be applied to sets defined by systems of inequalities involving polynomial or exponential functions. In particular, we describe an application to a problem of structural complexity in the Blum-Shub-Smale model of computation over the reals.