Microsoft researchers prove 31-year-old KLS conjecture with human-directed AI agents
Microsoft Research · rss · 2026-10-22
Microsoft researcher Xinzhi Zhang and a collaborator have proved the Kannan–Lovász–Simonovits (KLS) conjecture, posed in 1995 and regarded as one of the central open problems in high-dimensional convex geometry.
The conjecture: for a broad class of high-dimensional log-concave distributions, the best flat hyperplane cut approximates the best cut of any shape within a universal constant, independent of dimension — a dimension-free geometric principle with consequences for statistics, optimization, algorithms and sampling theory.
How it was proved:
- Starting from the best known July 2026 bound, AI agents explored 100+ candidate approaches (many involving lengthy higher-order tensor calculations), yielding a new mathematical criterion that became the foundation of the proof;
- The criterion could be applied recursively, tightening the bound down to an iterated logarithm dependence;
- Inspired by the authors' fast linear-programming algorithms, they repeated the whole recursive refinement and proved accumulated errors stay bounded by a universal constant, removing dimension dependence entirely.
Human–AI collaboration: rather than one end-to-end frontier-model run, the authors used human-directed agentic search — agents explored variations in parallel while the researcher pruned and redirected. An unguided baseline with roughly the same token budget failed.
Independent confirmation: two separate full proofs appeared the same day (one calling the Microsoft paper's first version "the crucial step"), plus a Lean 4 formalization; the authors also streamlined the proof and verified it in Lean.
More from AGI Musings
- Todd: putting your forecast numbers in writing is what really counts — ben_j_todd · 2026-10-23
- Humanities dissertations have collapsed, social sciences are next — with AI as one driver — gsiemens · 2026-10-23
- Greg Brockman: AI makes hacking 100x more profitable and easier, upending hacker economics — gabriel1 · 2026-10-23
- 'Nothing is real now on social media': viral demo shows AI-generated content everywhere — saibharadwaj · 2026-10-23
- Lilian Weng to Discuss Recursive Self-Improvement at SGLang Summit 2026 — BanghuaZ · 2026-10-23
- mmitchell_ai questions whether the AI safety vs security framing stems from EA — mmitchell_ai · 2026-10-23