Event Series
Event Type
Seminar
Thursday, November 11, 2021 3:00 PM
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 ∆, 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 ≤ (1-δ)m*(G), for arbitrary δ>0, where m*(G) is the matching number of G.
(ii) independent sets of a given size k, for all k ≤ (1-δ)α(∆), for arbitrary δ>0, where α(∆) is the NP-hardness threshold for this problem. 
 
Joint work with Will Perkins, Ashwin Sah, and Mehtaab Sawhney.