theaicatalog
Microsoft · Research

Microsoft Research team says it has proved the KLS conjecture

Microsoft Research says two researchers, including Xinzhi Zhang, have proved the Kannan-Lovász-Simonovits (KLS) conjecture, a problem proposed in 1995 about high-dimensional geometry and probability. The conjecture asks whether the best flat cut of a broad class of distributions is nearly as effective as the best cut of any shape, with the difference bounded by a constant that does not depend on the number of dimensions. The authors say they used AI agents in a human-directed search that explored roughly one hundred research trajectories, with researchers pruning weak paths and selecting promising ones. The post says a separate group of experts posted an independent full proof the same day, and a Lean 4 formalization was released later.