*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: Efficient High-dimensional Sampling and Integration
Ben Cousins
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.
