Final doctoral examination and defense of dissertation of Ben Cousins

SUMMARY: High-dimensional sampling and integration is a shining example of
the power of randomness in computation, where randomness provably helps.
Additionally, the theoretical advances for these problems seem to lead to
efficient algorithms in practice. The algorithms and techniques extend to a
variety of fields, such as operations research and systems biology.

The main contribution is an O*(n3) randomized algorithm for estimating the
volume of a well-rounded convex body, improving on the previous best
complexity of O*(n4). Previously, the known approach for potentially
achieving such complexity relied on a positive resolution of the KLS
hyperplane conjecture, a central open problem in convex geometry. Building
to this result, algorithmic improvements for Gaussian sampling and
integration are developed. A crucial algorithmic ingredient is analyzing an
accelerated cooling schedule with Gaussians that achieves a perfect
trade-off with the complexity of Gaussian sampling.

The theoretical insights transfer over to efficient algorithms in practice,
as is demonstrated by a MATLAB adaptation of the volume algorithm. The
performance vastly exceeds the current best deterministic algorithms.
Additionally, an implementation of the sampling algorithm, when applied to
systems biology for the analysis of metabolic networks, significantly
advances the frontier of computational feasibility.