Computer Science Speakers Series

Back to Listing

Theory Seminar: Nima Anari, "Entropic Independence in Combinatorial Distributions"

Event Type
Seminar/Symposium
Sponsor
Chandra Chekuri
Location
https://illinois.zoom.us/j/85236768481?pwd=RndkQzd2Vk5WMDNTdC9MQWZUemVjdz09
Virtual
wifi event
Date
Nov 1, 2021   10:00 am  
Views
42
Originating Calendar
Computer Science Speakers Calendar

Zoom URL: https://illinois.zoom.us/j/85236768481?pwd=RndkQzd2Vk5WMDNTdC9MQWZUemVjdz09

Meeting ID: 852 3676 8481

Password: theorycs

 

Speaker: Nima Anari

Title: Entropic Independence in Combinatorial Distributions

Abstract:

I will introduce a notion for combinatorial distributions that we call entropic independence. This notion is motivated by the desire to obtain tight mixing time bounds for natural random walks that can sample from these distributions. As is widely known in Markov Chain analysis, spectral analysis is often lossy (by polynomial factors) when the state space is exponentially large. Instead, Modified Log-Sobolev Inequalities (MLSI), which characterize the rate of entropy decay in a random walk, are a powerful family of inequalities that often yield the correct mixing time. We show that as long as the family of combinatorial distributions under study "accommodates weights”, entropic independence can be obtained with no extra effort from the much more manageable notion of spectral independence; the latter notion has been key to many breakthroughs in counting and sampling and has been unifying many classic Markov chain analysis techniques. I will talk about natural distributions where using our technique we obtain tight mixing time bounds for the first time: monomers in monomer-dimer systems, the high-temperature Ising model, the high-temperature hardcore model, and (non-symmetric) determinantal point processes. Time-permitting, I will briefly mention two further algorithmic applications of entropic independence: accelerating sampling time for multiple samples, and parallel algorithms for sampling determinant-based distributions.

link for robots only