Approximate counting and sampling via local central limit theorems

Approximate counting and sampling via local central limit theorems

Probability Seminar
Apr 27, 2022, 03:00 PM - 04:00 PM | Zoom Meeting ID: 985 7941 4748 Passcode: 783431 Evans Hall | Happening As Scheduled
Vishesh Jain, Stanford University

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