Posted on 10/23/2026 6:59:03 AM PDT by BenLurkin
For decades, a fundamental question about the difficulty of computing in high-dimensional spaces has resisted proof. New research resolves this question, removing a major theoretical obstacle to understanding the efficiency of randomized algorithms used across science and computing.
The Kannan–Lovász–Simonovits (KLS) conjecture was proposed in 1995. It asks whether, for a broad class of high-dimensional probability distributions, the best flat or hyperplane cut is always nearly as effective as the best cut of any shape. More precisely, KLS predicts that the two differ by no more than a universal constant, regardless of the number of dimensions. This would establish a dimension-free geometric principle with important consequences for high-dimensional geometry, probability, and theoretical computer science. Because the geometry of these cuts governs how quickly random walks can explore a distribution, KLS also plays a central role in the theory of high-dimensional sampling.
Since 1995, mathematicians have accumulated evidence that the conjecture was true, but a complete proof remained elusive. Now, two researchers, including Xinzhi Zhang from the Machine Learning and Optimization group at Microsoft Research, have proved the KLS conjecture(opens in new tab). They have shown that the relationship holds with a fixed bound, regardless of how many dimensions a shape has. Before this work, the best known result(opens in new tab), established in July 2026, allowed that bound to grow slowly as the number of dimensions increased. This work establishes a fundamental geometric principle: high-dimensional spaces are better behaved than previously known, and the obstacles to navigating them do not grow without bound as dimensions increase.
(Excerpt) Read more at microsoft.com ...
|
Click here: to donate by Credit Card Or here: to donate by PayPal Or by mail to: Free Republic, LLC - PO Box 9771 - Fresno, CA 93794 Thank you very much and God bless you. |
My Friday night bowling team solved that problem last winter.
It was so obvious.
Lemme get my calculator.
I always wondered about that too.
AI, which can make millions of calculations and permutations in seconds or minutes, is solving these “problems” and is putting academic mathamaticians out of work.
Building on the technical idea (Klartag’s exponential tilts) used by the AI to obtain the proof, the stated bound has been improved slightly by human mathematicians a few days later.
Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.
