Date & Time:
April 19, 2022 3:30 pm – 4:30 pm
Location:
Kent 107, 1020-24 East 58th St., Chicago, IL, 60637
04/19/2022 03:30 PM 04/19/2022 04:30 PM America/Chicago Nguyen Thuy Duong Vuong (Stanford) – Entropic Independence: Optimal Mixing of Local Random Walks Kent 107, 1020-24 East 58th St., Chicago, IL, 60637

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 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.

Host: Madhur Tulsiani

Speakers

Nguyen Thuy Duong Vuong

PhD Student, Stanford University

Thuy-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.

Related News & Events

Haifeng Xu
UChicago CS News

New CS and DSI Faculty Haifeng Xu Brings Strategic Intelligence to NeurIPS 2022

Nov 28, 2022
UChicago CS News

UChicago CS Research Finds New Angle on Database Query Processing with Geometry

Nov 08, 2022
UChicago CS News

Asst. Prof. Aloni Cohen Receives Award For Revealing Flaws in Deidentifying Data

Sep 09, 2022
UChicago CS News

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Aug 15, 2022
UChicago CS News

New 2022-23 Faculty Add Expertise in Linguistics, Visualization, Economics, and Data Science Education

Aug 11, 2022
In the News

UChicago Co-Leads $10 Million NSF Institute on Foundations of Data Science

Aug 09, 2022
In the News

Bill Fefferman Comments on New Standards for Quantum-Proof Cryptography

Jul 07, 2022
UChicago CS News

UChicago London Colloquium Features Data Science, Quantum Research

Jul 01, 2022
UChicago CS News

Faculty Bill Fefferman and Chenhao Tan Receive Google Research Scholar Awards

Jun 21, 2022
UChicago CS News

First-Year PhD Student Co-Authors Outstanding Paper Award Winner at TQC 2022

Apr 28, 2022
In the News

Quanta Magazine Features Prof. Bill Fefferman’s Work on Quantum Algorithms

Jan 20, 2022
UChicago CS News

In-Fridge Controller Could Scale Up Quantum Computers, Award-Winning UChicago Research Finds

Jan 10, 2022
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube