http://www.cc.gatech.edu/~bcousins/

Ph.D. Candidate in Algorithms, Combinatorics, and Optimization

School of Computer Science

College of Computing

Georgia Institute of Technology

bcousins3@gatech.edu


Date: Friday, April 28, 2017
Time: 10:30 AM
Location: Klaus 2100

Committee:
Dr. Santosh Vempala, School of Computer Science (Advisor)
Dr. Ton Dieker, Department of Industrial Engineering and Operations
Research, Columbia University
Dr. Dana Randall, School of Computer Science
Dr. Prasad Tetali, School of Mathematics
Dr. Eric Vigoda, School of Computer Science


Abstract: 

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*(n^3) randomized algorithm for estimating the
volume of a well-rounded convex body, improving on the previous best
complexity of O*(n^4). 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.