TCS+ talk: Wednesday, April 28 — Ronen Eldan, Weizmann Institute

by plustcs

The next TCS+ talk will take place this coming Wednesday, April 28th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Ronen Eldan from the Weizmann Institute will speak about “Localization, stochastic localization, and Chen’s recent breakthrough on the Kannan-Lovasz-Simonivits conjecture” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The recorded talk will also be posted on our website afterwards, so people who did not sign up will still be able to watch the talk) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

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.