[Colloquium] CS Seminar - Nguyen Thuy Duong Vuong April 19, 2022

[Jose J Fragoso]

UNIVERSITY OF CHICAGO

COMPUTER SCIENCE DEPARTMENT

PRESENTS



Nguyen Thuy Duong Vuong
Stanford University


 [cid:image001.jpg at 01D85008.3F3D92F0]

Tuesday, April 19, 2022 at 3:30pm
Kent Chemical Laboratory, Room 107

“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 using models whose interaction matrix has eigen spectrum lying within an interval of length smaller than 1, and for a variation of the Glauber dynamics to sample from 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.


Bio: NguyenThuy-Duong "June" Vuong is a third year PhD student at Stanford University, working with Nima Anari and Moses Charikar. She works on geometry of polynomials, with applications in sampling and optimization algorithms over combinatorial domain.



Host: Madhur Tulsiani




--
Jose J Fragoso
Project Assistant IV
Computer Science Department
5730 S. Ellis – Room 200C
Chicago, IL. 60637
jfragoso at uchicago.edu
(773) 702-6614
(773) 702-8487 FAX

[signature_1572818061]



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220415/6bcd6a5a/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 36362 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220415/6bcd6a5a/attachment-0001.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.png
Type: image/png
Size: 459521 bytes
Desc: image003.png
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220415/6bcd6a5a/attachment-0001.png>