Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1995 Copyright 1995 University of Bonn, Department of Computer Science, Abt. V
85145

Approximating the Volume of General Pfaffian Bodies
Marek Karpinski, Angus Macintyre
[Download PostScript] [Download PDF]

We introduce a new powerful method of approximating the volume (and integrals) of vast number of geometric bodies defined by boolean combinations of Pfaffian conditions. The method depends on the polynomial bounds on the VC - Dimensions of the classes of sets to be measured. The resulting approximation algorithms are quite different in spirit from the other up to now known mehtods, and gives efficient randomized solutions even for such seemingly untouchable problems of ststistical phzsics like computing the volume of sets defined by the systems of exponential and polynomial inqualities.

Last Change: 11/05/14 at 09:54:10
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V