School of Computer Science Professor Santosh Vempala and University of Washington Assistant Professor Yin Tat Lee recently discovered a breakthrough theorem that makes progress toward the KLS conjecture.
According to the KLS conjecture, the best way to cut the shape is to use a hyperplane up to a constant factor. A hyperplane is a straight-line cut in higher dimensions, a slice essentially. As long as the shape is convex, meaning every point can see every other point, it will be an effective cut. The surface area may not be the least, but it will be within a small factor of the best possible.
“The fact that a hyperplane is nearly optimal doesn’t change as the dimension goes up,” Vempala said.
Since the breakthrough In December 2016, published in a paper of their findings, Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion they have been asked to share their findings with mathematician s from across the country. Among these were presentations at the Mathematical Sciences Research Institute, the School of Mathematics Colloquium at Georgia Tech, and Current Developments in Mathematics – a joint annual conference organized by Harvard and MIT that highlights some of the biggest mathematical discoveries of the year where Vempala was the only computer scientist invited to present.
“Computer science has come of the age when its findings are of interest for their mathematics depth alone,” Vempala said. The KLS conjecture was first posited in 1995 by Ravindran Kannan, László Lovász, and Miklós Simonovits, whom it was named after. Since then, mathematicians have been trying to find what this constant is. Vempala and Lee proved the surface area could be no worse than the dimension to the power of a quarter — even as the dimension increases.
“During the last few decades, the KLS conjecture has been studied for many special cases and is becoming perhaps the most fundamental questions in high-dimensional geometry,” Lee said. “Given the importance of convexity in both mathematics and computer science in general, and given how natural is the statement of KLS conjecture, we believe both our result and our techniques will be significant to not just theoretical computer science but many fields across subjects.”
Their discovery improves on the best known bound for the constant, and as a consequence improves on the complexity of sampling and on the bounds for several other parameters in the field of convex geometry, and establishes tight bounds for others.
Kannan – the K in KLS – currently a principal researcher at Microsoft Research India and distinguished visiting scientist at the Simons Institute Berkeley, notes this result makes considerable progress on the conjecture.
"Lee and Vempala’s result on the KLS conjecture is an important milestone,” Kannan said. “They use a fundamental scheme of 'Gaussian cooling’ (to transform any distribution into a Gaussian or vice versa) developed in earlier work of Santosh’s to gradually reduce the problem to the simple Gaussian case.
“They give a beautiful proof that this reduction does not degrade the 'isoperimetric constant,’ which is central to the conjecture. The combination of mathematical and algorithmic techniques is very impressive."
Mathematicians have stated that the result is just one of the breakthroughs. “What is even more important than the result itself is the method of proof,” said Mark Rudelson, a mathematics professor at the University of Michigan. “This new localization method may have applications going far beyond the original problem it was created for.”
They also recognize that this discovery bridges mathematics and computer science and will have impact for years to come. “This conjecture is important in both pure mathematics and theoretical computer science, and the remarkable work of Lee and Vempala exemplifies the deep synergy between these two fields," said Assaf Naor, a professor at Princeton’s Department of Mathematics.
“By building on insights of Eldan, they improved the previously best-known (and hard-fought) bound in the KLS conjecture, obtained better algorithms, and elucidated a powerful method which they have continued to use elsewhere and will undoubtedly be a fundamental tool in future investigations.”
Vempala and Lee are researching how the conjecture relates to manifold (curved) spaces. This has led to a faster method for sampling and computing volumes of polytopes (geometric shapes with flat sides) in high dimension. Vempala will present the team's findings at UC Berkeley, Stanford University, and at the Building Bridges II conference in Budapest in July.
]]>tess.malone@cc.gatech.edu
]]>