To Cheer You Up in Difficult Times 15: Yuansi Chen Achieved a Major Breakthrough on Bourgain’s Slicing Problem and the Kannan, Lovász and Simonovits Conjecture

Yuansi Chen

This post gives some background to  a recent amazing breakthrough  paper: An Almost Constant Lower Bound of the Isoperimetric Coefficient in the KLS Conjecture by Yuansi Chen. Congratulations Yuansi!

The news

Yuansi Chen gave an almost constant bounds for Bourgain’s 1984 slicing problem and for the Kannan-Lovasz-Simonovits 1995 conjecture. In this post I will describe these conjectures.

Unrelated cheerful news: Here is a very nice Quanta article by Kevin Hartnett on Lauren Williams, the positive Grassmannian and connections to physics. (See this related 2015 post.)

Bourgain’s slicing problem

Bourgain’s slicing problem (1984):  Is there c > 0 such that for any dimension n and any centrally symmetric convex body K ⊆ of volume one, there exists a hyperplane H such that the (n − 1)-dimensional volume of K ∩ H is at least c?

Vitali Milman wrote: “I was told once by Jean that he had spent more time on this problem and had dedicated more efforts to it than to any other problem he had ever worked on.”  

A positive answer to the problem is sometimes referred to as the hyperplane conjecture. Bourgain himself proved in the late 1980s that  the answer is yes if and twenty years later Boaz Klartag shaved away the logn factor. For more on the problem see this article by Boaz Klartag and Vitali Milman and for the history see the moving foreword  by Vitali Milman.

Yuansi Chen’s result (combined with an earlier result of Klartag and Ronen) asserts that c can be taken as .

Computing the volume of convex sets and the 1995 Kannan-Lovasz-Simonovits conjecture

Kannan, Lovász and Simonovits (KLS) conjectured  in 1995 that for any distribution that is
log-concave, the Cheeger isoperimetric coefficient equals to that achieved by half-spaces up to a universal constant factor.  The crucial point here is that the constant does not depend on the dimension.

Let K be a convex body of volume one in and consider the uniform probability distribution on K. Given a subset A of K of volume t≤1/2 we can ask what is the surface S(A) area of . (We don’t want to consider points in the surface of itself.)   Let be the minimum value of S(A) for subsets of volume t. The Cheeger constant or the expansion constant is the minimum value of f(t)/t. The KLS conjecture asserts that up to a universal constant independent from the dimension the Cheeger constant is realized by separating K with a hyperplane! (The conjecture is also called the Kannan, Lovász and Simonovits hyperplane conjecture.)

The motivation for the KLS conjecture came from a major 1990 breakthrough in the theory of algorithms. Dyer, Frieze, and Kannan found a polynomial-time algorithm to compute the volume of a convex set K in .  Kannan, Lovász and Simonovich (later joined by Santosh Vampala) wrote a series of ingenious papers where they improved the exponents of the polynomial and in the process introduced new methods for proving rapid mixing of Markov chains and new Euclidean isoperimetric results and conjectures.

As it turned out the KLS conjecture implies Bourgain’s hyperplane conjecture and also the “thin-shell conjecture” that  I will not describe here.

Yuansi Chen’s proved  an almost constant lower bound of the isoperimetric coefficient in the KLS conjecture!

This also gives faster mixing time bounds of Markov chain Monte Carlo (MCMC) sampling algorithms on log-concave measures.

Ronen Eldan‘s  stochastic localization scheme and the strategy proposed by Yin Tat Lee and SantoshVempala

Yuansi Chen’s proof relies on Ronen Eldan‘s  stochastic localization scheme that was introduced in this 2013 paper

Ronen Eldan, Thin shell implies spectral gap up to polylog via a stochastic localization scheme

It follows a strategy laid by Yin Tat Lee and Santosh Vempala 2017 FOCS paper

Y. T. Lee and S. S. Vempala,  Eldan’s stochastic localization and the KLS hyperplane conjecture: an improved lower bound for expansion.

There is not much more I can tell you now about Ronen’s theory, about Yin Tat and Santosh’s strategy, about Yuansi’s proof, and about further intermediate results. (This post here might be somewhat related to Ronen’s method.) But let me very briefly mention a few related matters.

1. There are interesting negative results regarding volume computations, see the 1987 Barany Furedi’s paper and Ronen Eldan’s 2009 paper
2. It is a very interesting question (that I heard from Moshe Vardi) to understand the connection between practice and theory regarding Markov chain Monte Carlo
   (MCMC) sampling algorithms e.g. for approximating permanents and volumes.
3. Related topics are: Dvoretzky’s theorem, Milman’s theorem, isotropic position, the concentration of measure phenomenon, asymptotic convex geometry.

The Busseman-Petty problem

The Busseman-Petty problem from 1956 asks whether it is true that a symmetric convex body with larger central hyperplane sections has a larger volume. So the question was  if K and L are centrally symmetric problems and all hyperplane sections of K (through the origin)  have a larger volume than those of L, is it true that the volume of K is larger than that of L.  Busemann and Petty showed that the answer is positive if K is a ball. (A positive answer when L is a ball would have given a very strong version of the slicing conjecture.) But the answer is negative for dimensions larger than or equal to 5.

Here is a brief history:

Larman and Rogers constructed a counterexample in dimension 12 in their example L was a ball and K was a perturbation of a ball. Ball showed that taking L to be a ball and K the standard cube gives a counterexample in dimension 10;  Giannopoulos and Bourgain gave counterexamples in dimension 7   and Papadimitrakis finally found a counterexample in dimension 5. Gardner gave a  positive for answer for dimensions 3  Zhang gave a positive solution for dimension 4. Erwin Lutwak’s theory of intersection bodies plays an important role in the solution.  Gardner, Koldobskiy, and Schlumprecht presented a unified solution in all dimensions.

This is a really beautiful story and was saw a slice of the story in our second “test your intuition”.  In the late 90s I had a “what is new” corner on my homepage and I remember devoting it to some of these developments.

Sources: Gardner’s book “Geometric tomography“, and Koldobskiy’s book “Fourier analysis in convex geometry”.

Here are very nice slides from a lecture of Alexandr Koldobskiy on the problem that also contain some information on the slicing problem.

2016 meeting: Approximate Counting, Markov Chains and Phase Transitions;  Series of 2019 lectures in Atlanta on related matters. ( Koldobsky I,II,III ; Werner; Paouris)