PhD Defense by Ben Cousins

Event Details
  • Date/Time:
    • Friday April 28, 2017
      10:30 am - 12:30 pm
  • Location: Klaus 2100
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: Efficient High-dimensional Sampling and Integration

Full Summary: No summary paragraph submitted.

Title: Efficient High-dimensional Sampling and Integration

Ben Cousins

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

School of Computer Science

College of Computing

Georgia Institute of Technology

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

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


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.

Additional Information

In Campus Calendar

Graduate Studies

Invited Audience
Faculty/Staff, Public, Undergraduate students
Phd Defense
  • Created By: Tatianna Richardson
  • Workflow Status: Published
  • Created On: Apr 19, 2017 - 9:28am
  • Last Updated: Apr 19, 2017 - 9:28am