ProbXiv
Explorersign in
Problem archiveProblem record

Statement

The KLS conjecture is stated by Kannan, Lovász and Simonovits [1] as follows. Main text: Given a distribution, the isoperimetric coefficient of a subset is the ratio of the measure of the subset boundary to the minimum of the measures of the subset and its complement. Taking the minimum of such ratios over all subsets defines the isoperimetric coefficient of the distribution, also called the Cheeger isoperimetric coefficient of the distribution. Kannan, Lovász and Simonovits (KLS) [1] conjecture that for any distribution that is log-concave, the Cheeger isoperimetric coefficient equals to that achieved by half-spaces up to a universal constant factor. If the conjecture is true, the Cheeger isoperimetric coefficient can be determined by going through all the half- spaces instead of all subsets. For this reason, the KLS conjecture is also called the KLS hyperplane conjecture. To make it precise, we start by formally defining log-concave distributions and then we state the conjecture. A probability density function p : Rd \to R is log-concave if its logarithm is concave, i.e., for any x, y \in Rd \times Rd and for any \lambda \in [0, 1], (1) p(\lambdax + (1 − \lambda)y) \geq p(x)\lambda p(y)1−\lambda . Common probability distributions such as Gaussian, exponential and logistic are log-concave. This definition also i

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.