Yin Tat Lee (Univ. Washington)

Oct 16, 2017.

Title and Abstract

Kannan-Lovasz-Simonovitz (KLS) conjecture

Kannan-Lovasz-Simonovitz (KLS) conjecture asserts that the isoperimetric constant of any isotropic convex set is uniformly bounded below.

It turns out that this conjecture implies several well-known conjectures from multiple fields: (Convex Geometry) Each unit-volume convex set contains a constant area cross section. (Information Theory) Each isotropic logconcave distribution has O(d) KL distance to standard Gaussian distribution. (Statistics) A random marginal of a convex set is approximately a Gaussian distribution with 1/sqrt(d) error in total variation distance. (Measure Theory) Any function with Lipschitz constant 1 on an isotropic logconcave distribution is concentrated to its median by O(1).

In this talk, we will discuss the latest development on the KLS conjecture.

Joint work with Santosh Vempala.


Yin Tat Lee is an assistant professor in the Paul G. Allen School of Computer Science & Engineering at the University of Washington. He received his PhD from MIT in 2016. His research interests are primarily in algorithms and they span a wide range of topics such as convex optimization, convex geometry, spectral graph theory, and online algorithms