[Theory] UC Theory Seminar

[Alexander Razborov]

Departments of Mathematics & Computer Science
Combinatorics & Theory Seminar

Tuesday, April 19, 3:30pm
Location Kent 107

June Vuong (Stanford)

TITLE: Entropic Independence: Optimal Mixing of Local Random Walks

ABSTRACT: In this talk, we will define a notion called entropic 
independence that is an entropic analog of spectral notions of high 
dimensional expansion. Informally, entropic independence of a background 
distribution µ on k-sized subsets of a ground set of elements says that 
for any (possibly randomly chosen) set S, the relative entropy of a 
single element of S drawn uniformly at random carries at most O(1/k) 
fraction of the relative entropy of S, a constant multiple of its “share 
of entropy.” Entropic independence is the natural analog of the recently 
established notion of spectral independence, if one replaces variance by 
entropy. Similar to how spectral independence is used to establish lower 
bounds on the Poincare constant of certain local random walks, we show a 
general way to derive lower bounds on the modified log Sobolev constant 
of these random walks using entropic independence.
Our main applications include tight mixing time bounds for Glauber 
dynamics on Ising models whose interaction matrix has eigenspectrum 
lying within an interval of length smaller than 1, and for a variation 
of the Glauber dynamics to samplefrom the hardcore model on general 
graphs.up to the tree-uniqueness threshold. These results give a 
quadratic improvement over previously best bounds on the mixing time of 
these random walks.
Based on joint work with Nima Anari, Vishesh Jain, Frederic Koehler, and 
Huy Tuan Pham. To appear at STOC 2022.