BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Kuikui Liu (University of Washington) DTSTART:20211110T180000Z DTEND:20211110T190000Z DTSTAMP:20260423T021018Z UID:TCSPlus/32 DESCRIPTION:Title: Spectral Independence: A New Tool to Analyze Markov Chains\nby Kuikui Liu (University of Washington) as part of TCS+\n\n\nAbstract\nMarkov chai n Monte Carlo is a widely used class of algorithms for sampling from high- dimensional probability distributions\, both in theory and in practice. Wh ile simple to implement\, analyzing the rate of convergence to stationarit y\, i.e. the "mixing time"\, remains a challenging problem in many setting s. We introduce a new technique to bound mixing times called "spectral ind ependence"\, which says that certain pairwise correlation matrices all hav e bounded spectral norm. This surprisingly powerful technique originates i n the emerging study of high-dimensional expanders\, and has allowed us to "unify" nearly all existing approaches to approximate counting and sampli ng by building new connections with other areas\, including statistical ph ysics\, geometry of polynomials\, functional analysis\, and more. Through these connections\, several long-standing open problems have recently been answered\, including counting bases of matroids and optimal mixing of the Glauber dynamics/Gibbs sampler up to the algorithmic phase transition thr eshold. \n\nBased on several joint works with Dorna Abdolazimi\, Nima Anar i\, Zongchen Chen\, Shayan Oveis Gharan\, Eric Vigoda\, Cynthia Vinzant\, and June Vuong.\n LOCATION:https://researchseminars.org/talk/TCSPlus/32/ END:VEVENT END:VCALENDAR