DMS Combinatorics Seminar

Speaker: Manuel Fernandez (Georgia Tech)

Title: On the \(\ell_0\)-Isoperimetry of Measurable Sets

Abstract: Gibbs-sampling, also known as coordinate hit-and-run (CHAR), is a random walk used to sample points uniformly from convex bodies. Its transition rule is simple: Given the current point p, pick a random coordinate i and resample the i'th coordinate of p according to the distribution induced by fixing all other coordinates. Despite its use in practice, strong theoretical guarantees regarding the mixing time of CHAR for sampling from convex bodies were only recently shown in works of Laddha and Vempala, Narayanan and Srivastava, and Narayanam, Rajaraman and Srivastava. In the work of Laddha and Vempala, as part of their proof strategy, the authors introduced the notion of the \(\ell_0\) isoperimetric coefficient of a measurable set and provided a lower bound for the quantity in the case of axis-aligned cubes. In this talk we will present some new results regarding the \(\ell_0\) isoperimetric coefficient of measurable sets. In particular we pin down the exact order of magnitude of the \(\ell_0\) isoperimetric coefficient of axis-aligned cubes and present a general upper bound of the \(\ell_0\) isoperimetric coefficient for any measurable set. As an application, we will mention how the results give a moderate improvement in the mixing time of CHAR.