Alexander Barvinok, University of Michigan

Abstract

In a joint work with Mark Rudelson, we present a simple formula to approximate the volume of a bounded polyhedron, defined as the intersection of the non-negative orthant and an affine subspace. The formula requires computing the analytic center of the polyhedron (the point maximizing the sum of the logarithms of the coordinates), which is also the solution to an entropy maximization problem (find the maximum entropy distribution on the non-negative orthant with the expectation in the affine subspace). The formula approximates the volume within a multiplicative factor of gamma^m, where gamma>0 is an absolute constant and m is the codimension of the subspace. Although the result is related to the slicing conjecture, the proof is quite simple, since we deal with a very special case and do not need the conjecture in its whole generality.

[Video]