Abstract

We observe a correspondence between analytic properties of multi-affine homogeneous polynomials, and combinatorial and spectral properties of "high-dimensional expanders", which are extensions of usual expander graphs to hypergraphs. We show that complete log-concavity corresponds to strong expansion properties of the associated hypergraphs. Implications include new mixing time bounds for combinatorially defined Markov chains. Algorithmic applications to approximate counting and sampling problems will be discussed.

Video Recording