Solving a 31-year-old grand challenge in mathematics – the KLS conjecture

Solving a 31-year-old grand challenge in mathematics – the KLS conjecture - Microsoft Research

Research

Publications Code, datasets and models

Artificial intelligence Audio & acoustics Computer vision Graphics & multimedia Human-computer interaction Human language technologies Search & information retrieval

Data platforms and analytics Hardware & devices Programming languages & software engineering Quantum computing Security, privacy & cryptography Systems & networking

Algorithms Mathematics

Ecology & environment Economics Medical, health & genomics Social sciences Technology for emerging markets

Academic programs Events & academic conferences Microsoft Research Forum

Microsoft Research Blog Microsoft Research Podcast Microsoft Research Stories

About Microsoft Research Careers & internships People News & awards

AI for Science Asia-Pacific Cambridge Catalyst Lab India Montreal New England New York City Redmond Other research groups

Register: Research Forum

Microsoft Security Azure Dynamics 365 Microsoft 365 Microsoft Teams Windows 365

Microsoft AI Azure Space Mixed reality Microsoft HoloLens Microsoft Viva Quantum computing Sustainability

Education Automotive Financial services Government Healthcare Manufacturing Retail

Find a partner Become a partner Partner Network Microsoft Marketplace Software companies

Blog Microsoft Advertising Developer Center Documentation Events Licensing Microsoft Learn Microsoft Research

View Sitemap

Return to Blog Home Microsoft Research Blog

Microsoft researcher and collaborator combine new mathematical ideas with human-directed AI to resolve a central problem in high-dimensional geometry and probability

At a glance

Fundamental scientific breakthrough: Researchers resolved the Kannan-Lovász-Simonovits (KLS) conjecture, a 31-year-old problem widely regarded as one of the central open questions in high-dimensional geometry, with implications for statistics, optimization, algorithms, and computer science.

A universal geometric principle: The result establishes a universal geometric principle for log-concave distributions, showing that simple flat cuts can capture their narrowest bottlenecks within a fixed factor, regardless of dimension.

Human-AI collaboration: The breakthrough emerged from a human-directed agentic research process in which AI systems explored mathematical possibilities while researchers evaluated, pruned, and redirected the search.

Independent confirmation: Multiple independent researchers have validated this research, identifying its central criterion as the key breakthrough, followed by a machine-checked formal verification.

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.

Figure 1: An illustration of the KLS Conjecture (simplified) on regular tetrahedron.

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.

PODCAST SERIES

AI Testing and Evaluation: Learnings from Science and Industry

Discover how Microsoft is learning from other domains to advance evaluation and testing as a pillar of AI governance.

Listen now

Opens in a new tab

The importance of the KLS conjecture was recognized across the field long before it was resolved. In its 2017-18 Annual Report, the Mathematical Sciences Research Institute (MSRI) (opens in new tab) called it “a central open problem in high-dimensional convex geometry.” The Simons Institute (opens in new tab) described it as “one of the most important open problems in convex geometry.” In the proceedings of the 2022 International Congress of Mathematicians (ICM) (opens in new tab) , Ronen Eldan noted its broad implications for high-dimensional convex and computational geometry. Quanta Magazine (opens in new tab) wrote that KLS “lies at the heart of many questions in statistics and computer science.”

Technical details

The authors began by improving the July 2026 result in order to make the mathematical bound more precise. Working with AI agents in a structured, human-directed process, they explored more than 100 candidate approaches, many involving lengthy calculations with higher-order tensors. This produced a new mathematical criterion that became the foundation of the final proof.

The authors then discovered that the new criterion could be applied recursively. Each improved bound could be fed back into the same argument to produce a still tighter one. In the October 1, 2026 version of the paper, this reduced the dependence on dimension to the iterated logarithm. This function grows extraordinarily slowly, but it still grows with the dimension and therefore did not yet fully resolve the conjecture.

The final step was to repeat the entire recursive refinement, rather than applying it only once. This idea was inspired by the authors’ earlier work on fast algorithms for linear programming. The authors...