Computer Science/Discrete Mathematics Seminar II

In the mid 80's, Bourgain asked the following question: Is there a universal constant $c>0$ such that every compact convex set $K$ in $R^n$, of unit volume, must contain a slice (namely, a set of the form $K \cap H$ for some affine hyperplane $H$) whose surface area is at least $c$?  

Due to its numerous implications and simple-to-state formulation, this question has become one of the central conjectures of convex geometry. Ten years later, Kannan-Lovasz and Simonovits proposed a related question, considering 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? This question has a direct implication on the complexity of many computational problems on convex sets and, moreover, it was shown to imply Bourgain's slicing conjecture. 

Very recently, Yuansi Chen obtained a striking breakthrough, nearly solving these two problems. In these two talks we aim to give an overview on the subject and, hopefully, a self contained proof of Chen's results. On the way towards the result, we will become familiar with the concept of "localization" (a very useful tool to prove concentration inequalities) and its extension, stochastic localization, the main technique used in the proof.

 This work is also surveyed in the recent quanta article: https://www.quantamagazine.org/statistics-postdoc-tames-decades-old-geometry-problem-20210301/