TCS+ Talk

Wednesday April 28, 2021 10:00 AM

Localization, stochastic localization, and Chen's recent breakthrough on the Kannan-Lovasz-Simonivits conjecture

Speaker: Ronen Eldan, Weizmann Institute
Location: Online Event

Abstract: The Kannan-Lovasz and Simonovits (KLS) conjecture considers the following isoperimetric problem on high-dimensional convex bodies: Given a convex body $K$, consider the optimal way to partition it into two pieces of equal volume so as to minimize their interface. Is it true that up to a universal constant, the minimal partition is attained via a hyperplane cut? Roughly speaking, this question can be thought of as asking "to what extent is a convex set a good expander"?

In analogy to expander graphs, such lower bounds on the capacity would imply bounds on mixing times of Markov chains associated with the convex set, and so this question has direct implications on the complexity of many computational problems on convex sets. Moreover, it was shown that a positive answer would imply Bourgain's slicing conjecture.  

Very recently, Yuansi Chen obtained a striking breakthrough, nearly solving this conjecture. In this talk, we will overview some of the central ideas used in the proof. We will start with the classical concept of "localization" (a very useful tool to prove concentration inequalities) and its extension, stochastic localization - the main technique used in the proof.

To watch the talk:

  • Watching the live stream. At the announced start time of the talk (or a minute before), a live video stream will be available on our "next talk" page. Simply connect to the page and enjoy the talk. No webcam or registration is needed. Questions and comments during the talk are welcome (text only, unfortunately); simply post a comment below the live video stream on YouTube.
  • Watching the recorded talk offline. The recorded talk will be made available shortly after the talk ends on our YouTube page. (Please leave a comment if you enjoyed it!)
Series TCS+ Talks

Contact: Bonnie Leung