微软研究员证明 KLS 猜想，破解 31 年高维几何难题

Techub News 消息，Microsoft Research 机器学习与优化组研究员张新智等人证明了提出已 31 年的 Kannan-Lovász-Simonovits（KLS）猜想。

这一猜想被认为是高维几何领域的核心开放问题，涉及统计学、优化、算法与计算机科学。新研究确立了对数凹分布的一个通用几何原理，表明无论维度多高，简单的平面切割都能在固定因子内捕捉其最窄瓶颈。

人机协作完成研究与验证

据介绍，这项突破来自人机协作的研究过程。研究人员引导 AI 系统探索数学上的可能性，并对结果进行评估、剪枝和方向调整。

目前，研究结果已获得多位独立研究者验证，并完成了机器检查的形式化验证。

移除随机算法效率的一项理论障碍

KLS 猜想于 1995 年提出。其证明移除了理解科学和计算中广泛使用的随机算法效率的一项主要理论障碍。

此前的最佳结果允许边界随维度增加而缓慢增长，而这项新工作证明该关系具有固定边界，也说明高维空间的行为比此前已知的更好。