Talks
Fall 2020

Approximate Counting and Sampling via Local Central Limit Theorems

Wednesday, Jan. 12, 2022 9:30 am10:20 am PST

Add to Calendar

Speaker: 

Vishesh Jain (Stanford University)

Location: 

Calvin Lab Auditorium

We introduce a framework for exploiting local central limit theorems as algorithmic tools. As applications, for general graphs $G$ with bounded maximum degree $\Delta$, we provide a deterministic fully polynomial time approximation scheme (FPTAS) (respectively, a quasi-linear time randomized algorithm) to count (respectively, sample from the uniform distribution on):
(i) matchings of a given size $k$, for all $k \leq (1-\delta)m^*(G)$, for arbitrary $\delta > 0$, where $m^*(G)$ is the matching number of $G$.
(ii) independent sets of a given size $k$, for all $k \leq (1-\delta)\alpha(\Delta)$, for arbitrary $\delta > 0$, where $\alpha(\Delta)$ is the NP-hardness threshold for this problem.
Joint work with Will Perkins, Ashwin Sah, and Mehtaab Sawhney.