# The Kannan-Lov'asz-Simonovits Conjecture

arXiv: https://arxiv.org/abs/1807.03465 · HTML: https://mlsanity.com/paper/1807.03465/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2018.

## Built on by (most cited first, 4 of 4)

- [Tester-Learners for Halfspaces: Universal Algorithms](https://mlsanity.com/paper/2305.11765/) (2023)
- [Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence](https://mlsanity.com/paper/2204.02570/) (2022)
- [Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser](https://mlsanity.com/paper/2305.06541/) (2023)
- [Improved generalization bounds for binary linear classification via isoperimetry](https://mlsanity.com/paper/2505.16713/) (2025)

## Abstract (arXiv)

The Kannan-Lov'asz-Simonovits conjecture says that the Cheeger constant of any logconcave density is achieved to within a universal, dimension-independent constant factor by a hyperplane-induced subset. Here we survey the origin and consequences of the conjecture (in geometry, probability, information theory and algorithms) as well as recent progress resulting in the current best bounds. The conjecture has lead to several techniques of general interest.