Microsoft Research team proves 31-year-old KLS conjecture in high-dimensional geometry

Researchers at Microsoft Research have proved the 31-year-old Kannan-Lovász-Simonovits, or KLS, conjecture, a long-standing open problem regarded as central to high-dimensional geometry. The work was led by Zhang Xinzhi and colleagues in the organization’s Machine Learning and Optimization group, according to Techub News. The result establishes a general geometric principle for log-concave distributions, showing that even in very high dimensions, simple hyperplane cuts can capture the narrowest bottleneck within a constant factor. The conjecture has implications across statistics, optimization, algorithms, and computer science. Techub said the breakthrough came out of a human-AI research process. Researchers guided an AI system to explore mathematical possibilities, then evaluated, pruned, and redirected those lines of inquiry. The result has since been checked by multiple independent researchers and also completed machine-checked formal verification. First proposed in 1995, the KLS conjecture had stood as a major theoretical barrier to understanding the efficiency of random algorithms widely used in science and computing. Earlier best-known results allowed the bound to grow slowly with dimension, while the new proof shows the relationship is bounded by a constant.