Talks
Spring 2019
Algorithmic Applications of Log-Concave Polynomials and High-Dimensional Expanders
Thursday, February 14th, 2019, 9:30 am–10:30 am
Speaker:
Kuikui Liu (University of Washington)
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.