Approximate Counting and Sampling via Local Central Limit Theorems

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.