Depois de 31 anos, um dos obstáculos mais famosos da matemática computacional foi superado. 🧮🧵 A conjectura KLS, central para entender cálculos em espaços de muitas dimensões, acaba de ganhar uma demonstração completa.

Imagem indisponível

A história começa em 1995. Os matemáticos Ravi Kannan, László Lovász e Miklós Simonovits formularam uma pergunta aparentemente geométrica — mas com impacto direto na forma como algoritmos exploram enormes volumes de possibilidades.

Imagine tentar se orientar numa cidade com milhares de dimensões. Parece absurdo, mas é exatamente o tipo de espaço usado para modelar dados, probabilidades, moléculas, sistemas físicos e problemas de otimização.

Imagem indisponível

A KLS perguntava se um corte simples, feito por um hiperplano, seria quase tão eficiente quanto qualquer corte complexo possível para dividir essas distribuições. A resposta demonstrada agora é: sim, com uma diferença limitada por uma constante.

Isso importa porque muitos algoritmos usam “passeios aleatórios”: eles dão passos ao acaso para explorar um espaço e obter amostras confiáveis. Se o espaço tiver gargalos difíceis, o processo pode ficar lento demais.

Imagem indisponível

Até pouco tempo, a melhor garantia conhecida piorava, ainda que lentamente, conforme o número de dimensões crescia. O novo trabalho mostra que esse obstáculo não aumenta sem limite — uma vitória para a teoria da amostragem e da otimização.

Xinzhi Zhang, da Microsoft Research, e seu coautor fecharam uma lacuna que atravessou gerações de pesquisa. Nem toda descoberta vira um produto amanhã — mas são resultados assim que tornam a computação mais previsível, eficiente e fundamentada.

Imagem indisponível