The KLS conjecture is stated by Kannan, Lovász and Simonovits [1] as follows.
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.