# Program of the Conference Convexity, probability and discrete structures, a geometric view point

Link to the main page of the conference.

#### Abstracts

##### Daniel Ahlberg, IMPA

Title: Continuum to discrete via double coin flips.

Abstract: Given a Boolean function, imagine you want to study its typical behaviour at a certain density $r=pq$, but do so by separately tossing a $p$-coin and a $q$-coin. We present an elementary variance formula which bounds the effect each coin has on the final outcome of the function. Via a similar two-stage construction of a Poisson point process, the analogous variance inequality allows for an efficient reduction of many continuum models in percolation theory to a familiar discrete setting, where a larger arsenal of techniques may be applied to study phenomena such as sharp thresholds and noise sensitivity.

##### Christine Bachoc, Université de Bordeaux

Title: Sets avoiding the distance 1 in ${\mathbb R}^n$.

Abstract: What is the supremum density of a measurable set in ${\mathbb R}^n$ avoiding distance 1? If the distance is the Euclidean distance, the answer is known only in the trivial case $n=1$. This problem is closely related to that of the determination of the chromatic number of Euclidean space, a surprisingly difficult problem even in dimension 2, which is open since it was posed by Nelson and Hadwiger in 1950. We will review recent results in this area, then we will discuss the case of a distance defined by a polytope. When the polytope tiles the space by translations, we conjecture that the answer is $2^{-n}$ and that the problem should be much easier that in the Euclidean setting. The case of the Voronoi polytopes associated to root lattices will be discussed.

##### Keith Ball, University of Warwick

Title: A reverse entropy power inequality.

Abstract: I shall explain a (near) analogue of Busemann's Theorem for the entropy of the marginals of a log-concave random vector.

##### Imre Bárány, Renyi Institute and University College London

Title: Volumes of convex lattice polytopes and a question of V. I. Arnold.

Abstract: Let $S(r,d)$ be the simplex ${\rm conv}(0,e_1,e_2,…,e_d)$ blown up by a factor $r$ ($r$ a positiv integer), and $A(r,d)$ its facet opposite to the origin. We are considering all convex lattice polytopes $P$ satisfying $A(r,d) \subset P \subset S(r,d)$. It will be shown that $d!{\rm vol}(P)$ takes every integer value between $c_dr^d$ and $r^d$, where $c_d$ is a positive constant depending only on $d$. The question has emerged in connection with a problem of V. I. Arnold on the number of (equivalence classes of) convex lattice polytopes of fixed volume in $R^d$.
Joint work with Liping Yuan.

##### Jop Briët, CWI, Amsterdam

Title: Hardness of Grothendieck Problems.

Abstract: Grothendieck’s inequality plays an important role in theoretical computer science. Algorithmic proofs show that some natural hard optimization problems admit efficient approximation algorithms whose quality is inversely proportional to the associated Grothendieck constant. Recently, Naor, Regev, and Vidick showed that the same is true for the non-commutative variant of the inequality.
We show that the non-commutative Grothendieck constant, which is known to equal 2, also precisely marks the threshold for efficient approximation algorithms. In particular, we prove that for any $\epsilon > 0$, it is NP-hard to approximate the non-commutative Grothendieck problem to within a factor $1/2 + \epsilon$, which matches the quality of the algorithm of Naor, Regev, and Vidick.
Our proof uses an embedding of $l_2$ into the space of matrices endowed with the trace norm with the property that the image of standard basis vectors is longer than that of unit vectors with no large coordinates.
Joint work with Oded Regev and Rishi Saket.

##### Ronen Eldan, Weitzmann Institute

Title: Multi-scale exploration of convex functions with applications to bandit convex optimization.

Abstract: Given a positive convex function $f$ defined on a convex domain $D$ in $R^n$, we construct a probability measure $\mu$ on $D$ with the following “exploration” property: for every $\varepsilon > 0$ and every function $g$ with $g(x) < -\varepsilon$ for some $x \in D$, the set where $f,g$ differ by $\varepsilon c_n$ has measure at least $c_n$ where $c_n$ is some constant depending only (and polynomially) on $n$. We will explain how this construction settles a long-standing gap in the theory of convex bandit optimization.
Joint work with Sebastien Bubeck.

##### Matthias Erbar, University of Bonn

Title: Curvature bounds for Markov chains via geodesic convexity: Consequences and examples.

Abstract: In this talk I will present a notion of curvature lower bounds that applies to Markov chains on discrete spaces. It is based on convexity properties of the Shannon entropy along geodesics in the space of probability measures with respect to a specific transport distance. In analogy to Ricci curvature lower bounds on manifolds, this notion implies a variety of functional inequalities such as Poincare, modified Log-Sobolev and entropy-transport cost inequalities. Other consequences include gradient estimates for the Markov semigroup and isoperimetric estimates in the underlying weighted graph. We will see examples of Markov chains with curvature bounds including random walks on permutations and (slices of) the cube as well as Glauber dynamics for spin systems.

##### Apostolos Giannopoulos, University of Athens

Title: Brascamp-Lieb inequality and quantitative versions of Helly's theorem.

Abstract: We discuss a number of new quantitative versions of Helly's theorem, due to Silouanos Brazitikos. For example, we show that for every family $\{P_i:i\in I\}$ of closed half-spaces $$P_i=\{ x\in {\mathbb R}^n:\langle x,w_i\rangle \leq 1\}$$ in ${\mathbb R}^n$ such that $P=\bigcap_{i\in I}P_i$ has positive volume, there exist $s\leq \alpha n$ and $i_1,\ldots , i_s\in I$ such that $$|P_{i_1}\cap\cdots\cap P_{i_s}|\leq (Cn)^n\,|P|,$$ where $\alpha , C>0$ are absolute constants. These results complement and improve previous work of Bárány-Katchalski-Pach and Naszódi. Our method combines the work of Srivastava on approximate John's decompositions with few vectors, a new estimate on the corresponding constant in the Brascamp-Lieb inequality and an appropriate variant of Ball's proof of the reverse isoperimetric inequality.

##### Nathaël Gozlan, Université Paris-Est Marne-la-Vallée

Title : Generalized transport costs and applications to concentration of measure.

Abstract: In this talk, I will present a new class of generalized optimal transport costs. I will discuss in particular several applications of these transport costs to the study of concentration of measure properties of discrete probability measures.
Based on joint works with C. Roberto, P-M Samson, Y. Shu, P. Tetali.

##### Alexander Kolesnikov, Higher School of Economics of Moscow

Title: Hessian metrics with application to functional inequalities.

Abstract: Hessian metrics are Riemannian metrics which have the form $g = D^2 \Phi$, where $\Phi$ is a convex function. They naturally appear in the theory of optimal transportation and Riemannian geometry. We discuss applications of Hessian metrics to convex geometry, in particular to log-Sobolev and Poincaré-type inequalities and global estimates for eigenvalues of the Monge-Ampere operator related to optimal transportation of log-concave measures.

Title: Influences for $3d$ percolation, a progress report.

Abstract: A standard Kahn-Kalai-Linial argument shows that the width of the critical window for percolation, in any dimension, is smaller than $1/\log n$. We show some partial results in the direction of improving this estimate.

##### Rafał Latała, University of Warsaw

Title: Upper and lower bounds for suprema of canonical processes.

Abstract: We consider the class of canonical processes $(X_t)$ of the form $X_t=\sum_{i=1}^{\infty}t_iX_i,$ where $X_i$ are independent random variables. If $X_i$ are standardized, i.e. have mean zero and variance one, then this series converges a.s. for $t\in \ell^2$ and we may try to estimate $b_X(T):=\mathbf{E}\sup_{t\in T} X_t\quad \mbox{for }T\subset \ell^2.$

We present a general upper bound for $b_X(T)$ based on Talagrand's generic chaining techniques and show that it may be reversed under the additional assumptions on the regularity of variables $X_i$. We also discuss a Sudakov-type minoration principle for canonical processes.
The talk is based on the joint work with Tomasz Tkocz.

##### James R. Lee, University of Washington

Title: Spectrahedral lifts of polytopes and combinatorial optimization.

Abstract: Much of the theory of mathematical programs for combinatorial optimization can be described in the following way: A polytope of interest has exponentially many (in the dimension) facets, but can be written as the linear projection of a simpler convex body in a higher-dimensional space. Simple might mean a polytope with a much smaller number of facets, or a spectrahedron (the intersection of an affine subspace with the PSD cone) of small dimension. This allows one to optimize linear functionals over the base polytope by instead optimizing a lifted functional over the lifted body. Unless P=NP, one does not expect certain polytopes–like the convex hull of indicators of traveling salesman tours in a graph–to have a small lift. But it remained open to prove any non-trivial lower bound on the necessary dimension for a spectrahedral lift, i.e. to prove that semi-definite programs do not yield efficient optimization procedures over these polytopes. We show that the cut, TSP, and stable set polytopes on n-vertex graphs are not the linear image of a spectrahedron of dimension less than $exp(n^c)$for some constant $c > 0$. In the process, many interesting phenomena emerge: Factorization of operators through the PSD cone, quantum information theory, discrete Fourier analysis, and real algebraic geometry.
This is based joint work with Prasad Ragahvendra and David Steurer.

##### Alexander Litvak, University of Alberta

Title: Invertibility of adjacency matrices of random digraphs.

Abstract: We show that an adjacency matrix of a random $d$-regular directed graph on $n$ vertices is invertible with probability at least $1-C(\ln^{3} d)/\sqrt{d}$ for $C\leq d\leq cn/\ln^2 n$.
Joint work with A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann and P. Youssef.

##### Mokshay Madiman, University of Delaware

Title: On the tendency to convexity of Minkowski sums.

Abstract: For a compact subset A of ${\mathbb R}^n$, let $A(k)$ be the Minkowski sum of $k$ copies of $A$, scaled by $1/k$. By a 1969 theorem of Emerson, Folkmann, Greenleaf, Shapley and Starr, $A(k)$ approaches the convex hull of $A$ in Hausdorff distance as $k$ goes to infinity. A few years ago, the speaker conjectured that the volume of $A(k)$ is non-decreasing in $k$, or in other words, that when the volume deficit between the convex hull of $A$ and $A(k)$ goes to $0$, it actually does so monotonically. While this conjecture holds true in dimension $1$ (as independently observed by F. Barthe) and for convex sets in any dimension (as observed with Bobkov and Wang), we show that it fails in dimension $12$ or greater. Then we consider whether one can have monotonicity of convergence of $A(k)$ when its non-convexity is measured in alternate ways. Our main positive result is that Schneider’s index of non-convexity of $A(k)$ converges monotonically to $0$ as $k$ increases; even the convergence does not seem to have been known before. As a by-product, we also obtain optimal rates of convergence. We also obtain some results for the Hausdorff distance to the convex hull, along the way clarifying various properties of these notions of non-convexity that may be of independent interest.
Joint work with Matthieu Fradelizi, Arnaud Marsiglietti, and Artem Zvavitch.

##### Dan Mangoubi, Hebrew University of Jerusalem

Title: Convexity phenomena in discrete harmonic functions.

Abstract: We study harmonic functions defined in $Z^d$. We define their $L^2$-growth in terms of the random walk, and show that it satisfies a strong convexity phenomenon. This is related to high powers of the Laplace operator and a discrete three circles theorem with an inherent error term. The error term exhibits a surprising gap phenomenon.
This is joint work with Gabor Lippner.

##### Arnaud Marsiglietti, University of Minnesota

Title: On the Brunn-Minkowski inequality for convex measures with applications to new isoperimetric inequalities.

Abstract: We prove that the inequality $$\mu((1-\lambda) A + \lambda B)^{1/n} \geq (1-\lambda)\mu(A)^{1/n} + \lambda \mu(B)^{1/n}$$ holds true for any unconditional log-concave measure $\mu$ and unconditional convex bodies $A,B \subset \mathbb{R}^n$. We also prove that the inequality holds true in the plane for any symmetric log-concave measure $\mu$ and symmetric convex bodies $A,B \subset \mathbb{R}^2$. As a consequence, we derive new isoperimetric inequalities.
Based on a joint work with G. Livshyts, P. Nayar and A. Zvavitch.

##### Quentin Mérigot, Université Paris Dauphine

Title: Discretization of convex functions and of the Monge-Ampère operator.

Abstract: Many problems in economy, geometry and mathematical physics can be phrased as the minimization of a functional over the space of convex functions, or over the space of convex bodies. In this talk, we will be interested in integral functionals that involve the Monge-Ampère operator of the convex function. Convexity constraints are notably difficult to handle numerically, but we will see that the Monge-Ampère operator will help us by playing the role of a barrier for the convexity constraints. We introduce a consistent discretization, which inherits convexity properties of the continuous variational problem, and show the effectiveness of our approach on the numerical simulations of nonlinear diffusion and crowd-motion models using the Jordan-Kinderlehrer-Otto minimizing-movement scheme.
Based on joint work with J.D Benamou, G. Carlier and É. Oudet.

##### Emanuel Milman, Technion IIT

Title: Spectral Estimates, Contractions and Hypercontractivity.

Abstract: Sharp comparison theorems are derived for all eigenvalues of the (weighted) Laplacian, for various classes of weighted-manifolds (i.e. Riemannian manifolds endowed with a smooth positive density). Examples include Euclidean space endowed with strongly log-concave and log-convex densities, extensions to $p$-exponential measures, unit-balls of $\ell_p^n$, one-dimensional spaces and Riemannian submersions. Our main tool is a general Contraction Principle for eigenvalues” on arbitrary metric-measure spaces. Motivated by Caffarelli's Contraction Theorem, we put forth several conjectures pertaining to the existence of contractions from the canonical sphere (and Gaussian space) to weighted-manifolds of appropriate topological type having (generalized) Ricci curvature positively bounded below; these conjectures are consistent with all known isoperimetric, heat-kernel and Sobolev-type properties, and would imply sharp conjectural spectral estimates on such spaces. Time permitting, we will provide an estimate on the trace of the associated heat-kernel assuming that the associated heat semi-group is hypercontractive, and describe a curious trichotomy for the heat-kernel.

##### Elchanan Mossel, UC Berkeley

Title: Harmonicity and Invariance on the slice.

Abstract: The subject of this talk is the slice of the discrete cube - i.e. the uniform distribution over all binary vector of a certain weight, or probabilistically the product measure on the cube conditioned on having a specific sum. I will review the $L_2$ theory of the slice as well as a the following new result: functions of low degree have similar distribution on the slice and the corresponding product measure on the cube.
Based on a joint work with Yuval Filmus (http://arxiv.org/abs/1507.02713).

##### Joe Neeman, UT Austin and Bonn

Title: rho-convexity.

Abstract: We say that a function of two real variables is rho-convex if its Hessian matrix, multiplied by rho on the off-diagonal, is positive semi-definite. This notion turns out to give simple proofs of various inequalities on Gaussian space – we will emphasize the Prekopa-Leindler inequality and Borell's “noise stability” inequality. On discrete spaces, the situation is much less clear but some things are still possible.
The presentation will include joint results with Anindya De and Elchanan Mossel.

##### Krzysztof Oleszkiewicz, University of Warsaw

Title: Strong contraction and influences in tail spaces.

Abstract: This is a joint work with S. Heilman and E. Mossel. We study strong contraction in the $L^p$ norm under a symmetric Markov semigroup and prove the degree one case of a conjecture of Mendel and Naor about heat smoothing in tail spaces under assumption that the semigroup satisfies the Poincare inequality. I will also briefly discuss negative answers to two related questions of Hatami and Kalai.

##### Grigoris Paouris, Texas A&M

Title: On Dvoretzky's theorem for subspaces of $L_p$.

Abstract: The “randomized” Dvoretzky's Theorem”, as proved by V. Milman, says that for every $\varepsilon>0$ and for every $n$-dimensional normed space, a “random subspace” of dimension $c(\varepsilon) k_X$ is $1+ \varepsilon$ isomorphic to Euclidean. The parameter $k_X$ is completely determined by the “global parameters of $X$”. In this talk I will discuss the function $c(\varepsilon)$ in the special cases of $\ell_p$ spaces and for subspaces of $L_p$.
The talk will be based on joint works with Petros Valettas and Joel Zinn.

##### Holger Rauhut, RWTH Aachen University

Title: Sparse and low rank recovery via null space properties.

Abstract: Compressed sensing is concerned with the recovery of a sparse signal from underdetermined linear measurements via efficient algorithms. This theory has been extended to the recovery of low rank matrices from incomplete measurements. The construction of optimal measurement matrices (maps) employs randomness. Often recovery guarantees for $l_1$-minimization and nuclear norm minimization are established via the restricted isometry property which is sufficient for recovery. In this talk, I will highlight that in important cases, the null space property (NSP) which is in fact also necessary for recovery, can be established directly via Mendelson's small ball method. For random matrices with independent entries, the NSP holds under significantly weaker conditions on the distribution. Moreover, in the matrix recovery case, it can be shown for random rank one measurements that are chosen at random from a so-called 4-design. In the sparse vector recovery case, we establish a version for $l_p$-constraint $l_1$-minimization with $p > 2$ which is important for quantized compressed sensing. In fact, related notions of the RIP only hold for a highly suboptimal number of measurements in this case.

##### Gideon Schechtman, Weitzmann Institute

Title: Metric $X_p$ inequalities.

Abstract: A nonlinear inequality of the flavour of the nonlinear version of the inequalities for type and cotype will be presented. This is a nonlinear extension of a linear inequality that was proved by Johnson, Maurey, Schechtman and Tzafriri in 1979 (and resembles the $X_p$ inequality of Rosenthal). The formulation (and proof) of the new inequality completes the search for bi-Lipschitz invariants that serve as an obstruction to the embeddability of $L_p$ spaces into each other, the previously understood cases of which were metric notions of type and cotype, which however fail to certify the nonembeddability of $L_q$ into $L_p$ when $2<q<p$. Among the consequences of the new inequality are new quantitative restrictions on the bi-Lipschitz embeddability into $L_p$ of snowflakes of $L_q$ and integer grids in $\ell_q^n$, for $2<q<p$.
Joint work with Assaf Naor.

##### Konstantin Tikhomirov, University of Alberta

Title: The smallest singular value of random matrices with heavy-tailed entries.

Abstract: We consider a classical problem of estimating the least singular value of random rectangular and square matrices with independent identically distributed entries. The novelty of our results consists primarily in imposing very weak moment assumptions on the distribution of the entries, which require special (new) techniques for dealing with “spikes”. Additionally, we will consider a question of Bai-Yin type convergence for the extremal singular values of rectangular matrices with i.i.d. log-concave rows.
The presentation will include joint results with Djalil Chafaï and Elizaveta Rebrova.

##### Frank Vallentin, University of Cologne

Title: Mathematical optimization for packing problems.

Abstract: How densely can one pack given objects into a given container? Such packing problems are fundamental problems in geometric optimization. Next to being classical mathematical challenges there are many applications in diverse areas such as information theory, materials science, physics, logistics, approximation theory.

Studying packing problems one is facing two basic tasks: Constructions: How to construct packings which are conjecturally optimal? Obstructions: How to prove that a given packing is indeed optimal?

For the first basic task researchers in mathematics and engineering found many heuristics which often work well in practice. In the talk I want explain computational tools for the second basic task. These tools are a blend of tools coming from infinite-dimensional semidefinite optimization and harmonic analysis, together with computational techniques coming from real algebraic geometry and polynomial optimization. I will report on computational results, which are frequently the best-known.

##### Roman Vershynin, University of Michigan

Title: Concentration of random graphs.

Abstract: Do random graphs concentrate near their expectations''? This question can be asked rigorously using matrices classically associated with graphs, namely the adjacency and Laplacian matrices. The answer depends on the sparsity of the graph. Relatively dense random graphs concentrate well. Sparse graphs do not, but they can be forced to concentrate. Theoretical analysis of concentration brings together tools from random matrix theory, combinatorics, and Grothendieck's inequalities. Practical motivation comes from analysis of networks, and in particular community detection problems.

##### Pierre Youssef, Université Paris Diderot

Title: Expansion and anti-concentration properties of random digraphs.

Abstract: Given a random $d$-regular directed graph with $n$ vertices and a subset $J$ of its vertices of size at most $n/d$, we show that the number of vertices connected to J is of almost maximal size with high probability. Moreover, if $\delta_i$ is the indicator of the event that vertex $i$ is connected to $J$, we show that $\delta=(\delta_1,\ldots, \delta_n)\in\{0,1\}^n$ is not concentrated around any vertex of the cube with high probability. These results are motivated by the study of the invertibility of the adjacency matrix which will be presented in A. Litvak's talk.
This is a joint work with A. Litvak, A. Lytova, K. Tikhomirov and N.Tomczak-Jaegermann.

##### Artem Zvavitch, Kent State University

Title: A discrete version of Koldobsky's slicing inequality.

Abstract: In this talk we will present an answer to a question of Alexander Koldobsky and present a discrete version of his slicing inequality: Let $\# K$ be the number of integer lattice points contained in a set $K$. We will show that for every natural number $d$ there exists a constant $C(d)$ such that for any origin-symmetric convex body $K \subset R^d$ $$\#K\leq C(d) \max_{\xi\in S^{d-1}} \left( \# (K\cap \xi^\perp)\right)\max \left \{\mbox{vol}_d(K)^{\frac{1}{d}},1\right\},$$ where $\xi^\perp$ is a hyperplane orthogonal to a unit vector $\xi$ and $C(d)$ can be chosen asymptotically of order $O(1)^{d}$. We will also discuss a number of special cases and generalizations of this inequality.
This is a joint work with Matthew Alexander and Martin Henk.