Sampling, counting, and local central limit theorems

Will Perkins University of Illinois at Chicago

Abstract

I will describe how local central limit theorems (and Fourier-analytic proofs of local central limit theorems) can be used to design fast sampling algorithms and deterministic approximate counting algorithms for the number of independent sets and matchings of a given size in bounded degree graphs. Joint work with Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney.

Date
Apr 12, 2022 3:30 PM — 5:00 PM
Event
Theory Seminar