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).