Invited Speakers:
- Santosh Vempala, Georgia Institute of Technology
- Title: The Interplay of Sampling and Optimization in High Dimension
- Abstract:
In the first part of this talk, we show how simulated annealing can be used for both logconcave sampling and convex optimization by varying parameter settings. The resulting algorithm for optimization can be viewed as an interior-point method needing only a membership oracle and achieving the same worst-case iteration complexity as the best possible barriers. In the second part, we present a faster sampling algorithm for polytopes which achieves subquadratic mixing time. The advantage of the algorithm, called geodesic gliding, comes from using non-Euclidean geometries where effects of the boundary are milder. Roughly speaking, geodesic gliding is an efficient discrete-time simulation of a stochastic differential equation on a Riemannian manifold whose metric is defined by the Hessian of a convex function.
The talk is based on joint works with Ben Cousins, Adam Kalai, Yin Tat Lee and Laci Lovasz.
- Timothy M. Chan, University of Waterloo
- Title: Computational Geometry, from Low to High Dimensions
- Abstract:
Abstract: Classical exact algorithms in computational geometry usually have run times that are exponential in the dimension. Recently, slightly subquadratic results have been found for some basic problems, such as offline orthogonal range search and offline Hamming nearest neighbor search, even when the dimension goes above logarithmic, surprisingly. I will survey these recent findings (including some work in progress and a new joint work with Josh Alman and Ryan Williams).
Along the way, we will see how old geometric divide-and-conquer ideas (variants of range trees and kd trees) can help solve nongeometric problems, such as all-pairs shortest paths, Boolean matrix multiplication, and 0-1 integer linear programming. In the opposite direction, we will also see how nongeometric techniques (fast matrix multiplication, circuit complexity, probabilistic polynomials, and Chebyshev polynomials) can help computational geometry. The latter techniques also give new results on offline approximate nearest neighbor search.