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

Two researchers, including Xinzhi Zhang of the Machine Learning and Optimization group at Microsoft Research, have proved the Kannan–Lovász–Simonovits conjecture, posting the complete argument in the October 4, 2026 version of their paper. The KLS conjecture dates to 1995 and concerns high-dimensional probability distributions: it asks whether the best flat or hyperplane cut through such a distribution is always nearly as effective as the best cut of any shape, differing by no more than a universal constant no matter how many dimensions are involved. The field had gathered evidence for the claim for three decades without a proof. Co-author Zhao Song is credited in the acknowledgements, alongside helpful discussions from Victor Reis and Ishai Menache.
The stakes are theoretical rather than immediately practical. KLS is a statement about log-concave distributions, a class that includes uniforms over convex bodies and many familiar bell-shaped curves. The geometry of flat cuts governs how quickly a random walk explores such a distribution, which puts the conjecture at the center of high-dimensional sampling theory. MSRI's 2017-18 annual report called it a central open problem in high-dimensional convex geometry, the Simons Institute described it as one of the most important open problems in convex geometry, and Ronen Eldan noted its broad implications in the 2022 International Congress of Mathematicians proceedings. Quanta Magazine has written that it lies at the heart of many questions in statistics and computer science.
The new work shows the relationship holds with a fixed bound independent of dimension. The best prior result, established in July 2026, allowed that bound to creep upward slowly as dimension increased. The proof removes that dependence entirely, which the authors frame as evidence that high-dimensional spaces are better behaved than previously understood.
How the argument was built is nearly as notable as the result. The authors started by sharpening the July 2026 bound, working with AI agents in a structured process directed by humans. That search covered more than 100 candidate approaches, many requiring lengthy computations with higher-order tensors, and yielded a new mathematical criterion that became the foundation of the proof. The authors then found the criterion could be applied recursively: each improved bound feeds back into the same argument to produce a tighter one. In the October 1 version, this pushed the dimension dependence down to the iterated logarithm, a function that grows so slowly it is nearly flat but not flat enough to settle the conjecture.
The decisive move was to repeat the whole recursive refinement rather than apply it once, an idea the authors trace to their earlier work on fast linear programming algorithms. They proved that the small errors introduced at each stage shrink fast enough that their cumulative total stays below a universal constant. That eliminated dimension dependence and closed the proof on October 4. The recursive method, its repetition, and the error-boundedness argument are original contributions. AI tools helped explore approaches, carry out derivations, prepare the manuscript and run internal proof checks; the researchers set direction, selected ideas, assembled the final argument and verified it.
Independent confirmation arrived quickly. On the same day the complete proof was posted, a separate group of leading experts published a full proof developed in parallel, building on the first version of the Microsoft paper and calling it the crucial step. A third proof appeared the same day relying on a closely related idea. A Lean 4 formalization was subsequently released, combining the key criterion from the first Microsoft paper with additional research. Independent proofs are among mathematics' strongest forms of validation because they show a result does not rest on a single chain of reasoning; formal verification in a proof assistant like Lean checks each step mechanically. The authors have also shortened their proof and verified the streamlined version in Lean, with plans to release both after final review.
The AI methodology is worth reading closely for anyone building agentic systems. Rather than prompting a frontier model end to end, the team ran parallel agents and had a researcher inspect intermediate output, discard unpromising directions and pass the strongest result into the next round. Roughly one hundred trajectories were explored before the key breakthrough. In a control track, repeated unguided attempts with several leading models, given roughly the same total token budget, fell short. The authors' own conclusion is that success depended on both the models' capabilities and human mathematical judgment.
This suggests a pattern for research-heavy tasks: search breadth supplied by agents, with a human acting as the selection function. A likely trade-off is throughput, since human review at every round limits how many branches can be pursued and requires expertise dense enough to judge partial results. The control track also indicates that token budget alone is a poor predictor of success on problems where the hard part is choosing which direction to develop.
What changes downstream is assumption cleanup. Many results in convex geometry, probability and theoretical computer science had been stated conditionally on KLS; they can now be stated unconditionally. In practice that is a stronger foundation rather than a new algorithm, though tighter sampling guarantees and their algorithmic consequences are the kind of follow-on a resolved conjecture typically enables. The authors are simplifying the proof and extending formal verification so the mathematics and theoretical computer science communities can examine and build on it.
Why it matters: theoretical computer scientists and statisticians gain an unconditional replacement for a three-decade-old assumption underpinning sampling and convex geometry, while teams building agentic AI tooling get a documented case of human-guided search outperforming unguided runs at similar token cost. My inference is that the methodology finding will draw more immediate commercial attention than the theorem itself, since it sketches a workflow rather than a result. It is also a reminder that formal verification is becoming part of how major mathematical claims are validated.
Based on reporting from the original publisher. Visit the source for full context and later updates.
Publisher excerpt
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 […] The post Solving a 31-year-old grand challenge in mathematics – the KLS conjecture appeared first on Microsof