Bourgain's slicing problem and KLS isoperimetry up to polylog
We prove that Bourgain's hyperplane conjecture and the Kannan-Lovász-Simonovits (KLS) isoperimetric conjecture hold true up to a factor that is polylogarithmic in the dimension.
Source author record
Bo'az Klartag
Bo'az Klartag appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
ResearcherUnclaimed source record
Catalog footprint
What is connected
20works
10topics
4close collaborators
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
20 published item(s)
preprint2022arXiv
Local tail bounds for polynomials on the discrete cube
Let $P$ be a polynomial of degree $d$ in independent Bernoulli random variables which has zero mean and unit variance. The Bonami hypercontractivity bound implies that the probability that $|P| > t$ decays exponentially in $t^{2/d}$. Confirming a conjecture of Keller and Klein, we prove a local version of this bound, providing an upper bound on the difference between the $e^{-r}$ and the $e^{-r-1}$ quantiles of $P$.
0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv
Discrete variants of Brunn-Minkowski type inequalities
We present an alternative, short proof of a recent discrete version of the Brunn-Minkowski inequality due to Lehec and the second named author. Our proof also yields the four functions theorem of Ahlswede and Daykin as well as some new variants.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
Remarks on curvature in the transportation metric
According to a classical result of E.~Calabi any hyperbolic affine hypersphere endowed with its natural Hessian metric has a non-positive Ricci tensor. The affine hyperspheres can be described as the level sets of solutions to the "hyperbolic" toric Kähler-Einstein equation $e^Φ = \det D^2 Φ$ on proper convex cones. We prove a generalization of this theorem by showing that for every $Φ$ solving this equation on a proper convex domain $Ω$ the corresponding metric measure space $(D^2 Φ, e^Φdx)$ has a non-positive Bakry-{É}mery tensor. Modifying the Calabi computations we obtain this result by applying the tensorial maximum principle to the weighted Laplacian of the Bakry-{É}mery tensor. Our computations are carried out in a generalized framework adapted to the optimal transportation problem for arbitrary target and source measures. For the optimal transportation of the log-concave probability measures we prove a third-order uniform dimension-free apriori estimate in the spirit of the second-order Caffarelli contraction theorem, which has numerous applications in probability theory.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
Super-Gaussian directions of random vectors
We establish the following universality property in high dimensions: Let $X$ be a random vector with density in $\mathbb{R}^n$. The density function can be arbitrary. We show that there exists a fixed unit vector $θ\in \mathbb{R}^n$ such that the random variable $Y = \langle X, θ\rangle$ satisfies $$ \min \left \{ \mathbb{P}( Y \geq t M ), \mathbb{P}(Y \leq -tM) \right \} \geq c e^{-C t^2} \qquad \qquad \text{for all} \ 0 \leq t \leq \tilde{c} \sqrt{n}, $$ where $M > 0$ is any median of $|Y|$, i.e., $\min \{ \mathbb{P}( |Y| \geq M), \mathbb{P}( |Y| \leq M ) \} \geq 1/2$. Here, $c, \tilde{c}, C > 0$ are universal constants. The dependence on the dimension $n$ is optimal, up to universal constants, improving upon our previous work.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Affine hemispheres of elliptic type
We find that for any n-dimensional, compact, convex subset K of R^{n+1} there is an affinely-spherical hypersurface M in R^{n+1} with center at the relative interior of K, such that the disjoint union of M and K is the boundary of an (n+1)-dimensional, compact, convex set. This so-called affine hemisphere M is uniquely determined by K up to affine transformations, it is of elliptic type, is associated with K in an affinely-invariant manner, and it is centered at the Santalo point of K.
0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv
Discrete curvature and abelian groups
We study a natural discrete Bochner-type inequality on graphs, and explore its merit as a notion of curvature in discrete spaces. An appealing feature of this discrete version seems to be that it is fairly straightforward to compute this notion of curvature parameter for several specific graphs of interest - particularly, abelian groups, slices of the hypercube, and the symmetric group under various sets of generators. We further develop this notion by deriving Buser-type inequalities (a la Ledoux), relating functional and isoperimetric constants associated with a graph. Our derivations provide a tight bound on the Cheeger constant (i.e., the edge-isoperimetric constant) in terms of the spectral gap, for graphs with nonnegative curvature, particularly, the class of abelian Cayley graphs - a result of independent interest.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
Eigenvalue distribution of optimal transportation
We investigate the Brenier map $\nabla Φ$ between the uniform measures on two convex domains in $\mathbb{R}^n$ or more generally, between two log-concave probability measures on $\mathbb{R}^n$. We show that the eigenvalues of the Hessian matrix $D^2 Φ$ exhibit remarkable concentration properties on a multiplicative scale, regardless of the choice of the two measures or the dimension $n$.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
Lipschitz functions on the infinite-dimensional torus
We discuss the spectrum phenomenon for Lipschitz functions on the infinite-dimensional torus. Suppose that $f$ is a measurable, real-valued, Lipschitz function on the torus $\mathbb{T}^{\infty}$. We prove that there exists a number $a \in \mathbb R$ with the following property: For any $ε> 0$ there exists a parallel, infinite-dimensional subtorus $M \subseteq \mathbb T^{\infty}$ such that the restriction of the function $f-a$ to the subtorus $M$ has an $L^{\infty}(M)$-norm of at most $ε$.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
Needle decompositions in Riemannian geometry
The localization technique from convex geometry is generalized to the setting of Riemannian manifolds whose Ricci curvature is bounded from below. In a nutshell, our method is based on the following observation: When the Ricci curvature is non-negative, log-concave measures are obtained when conditioning the Riemannian volume measure with respect to an integrable geodesic foliation. The Monge mass transfer problem plays an important role in our analysis.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
On the oscillation rigidity of a Lipschitz function on a high-dimensional flat torus
Given an arbitrary $1$-Lipschitz function $f$ on the torus $\mathbb{T}^n $, we find a $k$-dimensional subtorus $M \subseteq \mathbb{T}^n$, parallel to the axes, such that the restriction of $f$ to the subtorus $M$ is nearly a constant function. The $k$-dimensional subtorus $M$ is chosen randomly and uniformly. We show that when $k \leq c \log n / (\log \log n + \log 1/\varepsilon)$, the maximum and the minimum of $f$ on this random subtorus $M$ differ by at most $\varepsilon$, with high probability.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Concentration of measures supported on the cube
We prove a log-Sobolev inequality for a certain class of log-concave measures in high dimension. These are the probability measures supported on the unit cube in R^n whose density takes the form exp(-H) where the function H is assumed to be convex (but not strictly convex) with bounded pure second derivatives. Our argument relies on a transportation-cost inequality a la Talagrand.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Centroid Bodies and the Logarithmic Laplace Transform - A Unified Approach
We unify and slightly improve several bounds on the isotropic constant of high-dimensional convex bodies; in particular, a linear dependence on the body's psi-2 constant is obtained. Along the way, we present some new bounds on the volume of L_p-centroid bodies and yet another equivalent formulation of Bourgain's hyperplane conjecture. Our method is a combination of the L_p-centroid body technique of Paouris and the logarithmic Laplace transform technique of the first named author.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Inner Regularization of Log-Concave Measures and Small-Ball Estimates
In the study of concentration properties of isotropic log-concave measures, it is often useful to first ensure that the measure has super-Gaussian marginals. To this end, a standard preprocessing step is to convolve with a Gaussian measure, but this has the disadvantage of destroying small-ball information. We propose an alternative preprocessing step for making the measure seem super-Gaussian, at least up to reasonably high moments, which does not suffer from this caveat: namely, convolving the measure with a random orthogonal image of itself. As an application of this "inner-thickening", we recover Paouris' small-ball estimates.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Interpolations, convexity and geometric inequalities
We survey some interplays between spectral estimates of Hörmander-type, degenerate Monge-Ampère equations and geometric inequalities related to log-concavity such as Brunn-Minkowski, Santaló or Busemann inequalities.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Poincare Inequalities and Moment Maps
We propose a new method for obtaining Poincare-type inequalities on arbitrary convex bodies in R^n. Our technique involves a dual version of Bochner's formula and a certain moment map, and it also applies to some non-convex sets. In particular, we generalize the central limit theorem for convex bodies to a class of non-convex domains, including the unit balls of L_p-spaces in R^n for 0 < p < 1.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
Approximately gaussian marginals and the hyperplane conjecture
We discuss connections between certain well-known open problems related to the uniform measure on a high-dimensional convex body. In particular, we show that the "thin shell conjecture" implies the "hyperplane conjecture". This extends a result by K. Ball, according to which the stronger "spectral gap conjecture" implies the "hyperplane conjecture".
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
Quantum One-Way Communication is Exponentially Stronger Than Classical Communication
In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol communicating only $O(\log n)$ qubits, but for which any classical (randomized, bounded-error) protocol requires $\poly(n)$ bits of communication. That quantum protocol requires two rounds of communication. Ever since Raz's paper it was open whether the same exponential separation can be achieved with a quantum protocol that uses only one round of communication. Here we settle this question in the affirmative.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
Variations on the Berry-Esseen theorem
We analyze the quality of the gaussian approximation to linear combinations of n independent, identically-distributed random variables with finite fourth moments. It turns out that there exist universal, simple linear combinations that perform better than the sum of the variables. We also investigate the case in which the random variables are independent, yet they are not necessarily identically distributed.
0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv
Small ball probability and Dvoretzky theorem
Large deviation estimates are by now a standard tool inthe Asymptotic Convex Geometry, contrary to small deviationresults. In this note we present a novel application of a smalldeviations inequality to a problem related to the diameters of random sections of high dimensional convex bodies. Our results imply an unexpected distinction between the lower and the upper inclusions in Dvoretzky Theorem.
0 citations0 reviewsNo code linkedOpen access