Will Perkins (UIC) - Sampling, Counting, and Local Central Limit Theorems
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.
Host: Alexander Razborov
Speakers
Will Perkins
Will Perkins is an associate professor in the department of Mathematics, Statistics, and Computer Science at the University of Illinois at Chicago. Prior to this he was faculty at the University of Birmingham in the UK and a postdoc at Georgia Tech. He received his PhD in 2011 from the Courant Institute at New York University under the supervision of Joel Spencer. His research interests are in algorithms, probability, and combinatorics. One of his recent research directions is in developing methods in combinatorics and algorithms based on tools and intuition from statistical physics.
