Spring 2019

Algorithmic Applications of Log-Concave Polynomials and High-Dimensional Expanders

Thursday, February 14th, 2019 9:30 am10:30 am

Add to Calendar


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.