CUT THE ❌crap❌ CONVEX – PART 1

Penned By – Manav Bhavsar and Simran Jariwala

HOT NEWS?

HOT NEWS?

A postdoctoral statistician has surprised experts by solving one of the most important problems in high-dimensional convex geometry.

In the mid-1980s, the mathematician Jean Bourgain thought of a simple question about high-dimensional shapes and was stuck on it for the rest of his life.

Bourgain, who died in 2018, was one of the preeminent mathematicians of the modern era. A winner of the Fields Medal, mathematics’ highest honor He was known as a problem-solver extraordinaire, the kind of person you might talk to about a problem you’d been working on for months, only to have him solve it on the spot. Yet Bourgain could not answer his own question about high-dimensional shapes.

Bourgain had spent more time on this problem and had dedicated more efforts to it than to any other problem he had ever worked on. In the years since Bourgain formulated his problem, it has become the “opening gate” to understanding a wide range of questions about high-dimensional convex shapes — shapes that always contain the entire line segment connecting any two of their points. High-dimensional convex shapes are an important object of study not just for pure mathematicians but also for statisticians, machine learning researchers and other computer scientists working with high-dimensional data sets.

WHAT WAS THE PROBLEM?

Bourgain conjecture: “Is there c > 0 such that for any dimension n and any centrally symmetric convex body : K ⊆ Rⁿ of volume one, there exists a hyperplane H such that the (n − 1)-dimensional volume of K ∩ H is at least c?” , which boils down to the following simple question: Suppose a convex shape has volume 1 in your favorite choice of units. If you consider all the ways to slice through the shape using a flat plane one dimension lower, could these slices all have extremely low area, or must at least one be fairly substantial?

Bourgain guessed that some of these lower-dimensional slices must have substantial area. In particular, he conjectured that there is some universal constant, independent of the dimension, such that every shape contains at least one slice with an area greater than this constant.

WHAT IS SO SPECIAL ABOUT THIS PROBLEM?

At first glance, Bourgain’s conjecture might seem obvious to you. After all, if the shape were extremely skinny in every direction, how could it have enough substance to form one unit of volume? But the more you think about it, the more you understand how delicate it really is.

The difficulty is that high-dimensional shapes often behave in ways that defy our human, low-dimensional intuition. For example, for dimensions 10 and more, it is possible to build a cube and a sphere such that the cube has a larger volume than the sphere, but every slice through the center of the cube has a smaller area than the corresponding slice through the center of the sphere.

Bourgain’s slicing conjecture is a vote for high-dimensional tameness, a guess that high-dimensional shapes conform to our intuition in at least some ways.

Now, Bourgain’s guess has been vindicated: A paper posted online in November has proved, not quite Bourgain’s full conjecture, but a version so close that it puts a strict limit on high-dimensional weirdness, for all practical purposes.

Bourgain would have dreamt of achieving a result this strong!!

The latest paper, by Yuansi Chen, a postdoctoral researcher gets at the Bourgain slicing problem via an even more far-reaching question about convex geometry called the KLS conjecture. This 25-year-old conjecture, which asks about the best way to slice a shape into two equal portions, implies Bourgain’s conjecture.

 Moreover, the KLS conjecture lies at the heart of many questions in statistics and computer science, such as

• how long it will take for heat to diffuse through a convex shape
• how many steps a random walker must take from a starting point before reaching a truly random location.

Random walks are pretty much the only effective methods available for sampling random points and for a wide range of different computer science problems, the most important subroutine in the algorithm is, you want to sample a random point.

Chen’s new result gives instant improvements to the known running times of algorithms for tasks such as computing the volume of a convex shape or sampling from an assortment of machine learning models.  Chen’s work doesn’t quite prove the full KLS conjecture. But when it comes to computer science applications, we don’t need the full conjecture to get the full impact.

But What is KLS conjecture?

Let K be a convex body of volume one in Rⁿ 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 A ∩ int k. (We don’t want to consider points in the surface of K itself.) Let f_k(t) 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!

In simple words: Suppose you want to cut a convex shape, maybe an apple without dimples into two equal-size portions, and you’re planning to put one aside for later. The exposed surface is going to turn brown and unappetizing, so you want to make it as small as possible. Among all the possible cuts, which will minimize the exposed surface?

WANT TO KNOW HOW IT WAS SOLVED? Stay tuned! The mystery is about to be unveiled!

Let us know in the comments section below about your possible speculations!