The problem of algorithmically computing the volumes of
convex bodies is a well studied problem in combinatorics and theoretical
computer science. The best known results are perhaps those concerning
the use of Markov Chain Monte Carlo techniques for approximately
computing the volumes of general convex bodies. There are also results
of a different kind: Deterministic (approximate) computation of the
volumes of (certain)polytopes. In this direction, Alexander Barvinok and
John Hartigan gave an algorithm based upon the Maximum Entropy heuristic
from Statistical Physics that provides good approximations for certain
classes of polytopes, that includes the transportation polytopes.
The Maximum Entropy heuristic, originally introduced by Jaynes in 1957
says the following: Suppose one is faced with an unknown probability
distribution over a product space. Further suppose we know the
expectations of a certain number of random variables with respect to
this measure. Then the Maximum Entropy heuristic says that it ‘is
natural’ to work with that probability distribution that has max entropy
subject to the given linear constraints. Barvinok and Hartigan’s work
uses this idea and combines it with some fundamental results about the
computability of entropies of these max entropy distributions.
In this talk, I will show how to adapt this approach to Spectrahedra,
which are a naturally occurring class of convex sets, defined as slices
of the cone of Positive Semidefinite matrices. The case of spectrahedra
shows up several surprises. As a byproduct of this work it will follow
that central sections of the set of density matrices (the quantum
version of the simplex) all have asymptotically the same volume. This
allows for very general approximation algorithms, which apply to large
classes of naturally occurring spectrahedra. I will then give several
examples to illustrate the utility of this method.
This is joint work with Jonathan Leake (U Waterloo) and Mahmut Levent
Dogan (T U Berlin).