Imagine cutting a convex shape into two pieces of equal volume. The Kannan-Lovász-Simonovits (KLS) conjecture, proposed in 1995, asks whether the best flat cut is always nearly as good as the best cut of any shape, within a fixed factor that does not grow as the number of dimensions increases.
Microsoft Research's Xinzhi Zhang and collaborator Zhao Song have now proved it, in a paper titled "An O(1) Bound for the KLS Constant." The key was a new criterion that could be applied recursively, with each improved bound fed back into the argument until the dependence on dimension disappeared. AI agents explored more than 100 candidate approaches, while the researchers chose the directions and assembled and checked the proof.
Independent proofs appeared the same day, and a machine-checked version in the Lean 4 proof assistant followed. The result matters for high-dimensional sampling, statistics, optimization and computer science.
Source: Microsoft Research Blog, October 21, 2026 — https://www.microsoft.com/en-us/research/blog/solving-a-31-year-old-grand-challenge-in-mathematics-the-kls-conjecture
No comments:
Post a Comment