Approximate counting and sampling via local central limit theorems

DOI10.1145/3519935.3519957MaRDI QIDQ6083602zbMATH OpenOpenAlexFDO

Authors Vishesh Jain, Will Perkins, Ashwin Sah, Mehtaab Sawhney

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.01161, https://hdl.handle.net/1721.1/146422

zbMATH Keywords

approximate counting and samplinghard-core modelindependent setslocal central limit theoremsmatchings

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We give an FPTAS for computing the number of matchings of size $k$ in a graph $G$ of maximum degree $Delta$ on $n$ vertices, for all $kle(1-delta)m^{\ast }(G)$, where $delta>0$ is fixed and $m^{\ast }(G)$ is the matching number of $G$, and an FPTAS for the number of independent sets of size $kle(1-delta)alph{a}_c(Delta)n$, where $alph{a}_c(Delta)$ is the NP-hardness threshold for this problem. We also provide quasi-linear time randomized algorithms to approximately sample from the uniform distribution on matchings of size $kleq(1-delta)m^{\ast }(G)$ and independent sets of size $kleq(1-delta)alph{a}_c(Delta)n$. Our results are based on a new framework for exploiting local central limit theorems as an algorithmic tool. We use a combination of Fourier inversion, probabilistic estimates, and the deterministic approximation of partition functions at complex activities to extract approximations of the coefficients of the partition function. For our results for independent sets, we prove a new local central limit theorem for the hard-core model that applies to all fugacities below $lambd{a}_c(Delta)$, the uniqueness threshold on the infinite $Delta$-regular tree.

Cited in

(11)

• Local central limit theorems, the high-order correlations of rejective sampling and logistic likelihood asymptotics
• Approximating Large Frequency Moments with Pick-and-Drop Sampling
• On Local Distributed Sampling and Counting
• Deterministic approximate counting of colorings with fewer than 2 colors via absence of zeros
• Hypergraph independence polynomials with a zero close to the origin
• Fast and slow mixing of the Kawasaki dynamics on bounded-degree graphs
• On the evolution of structure in triangle-free graphs
• Rapid mixing of the down-up walk on matchings of a fixed size
• Toward derandomizing Markov chain Monte Carlo
• Parameter estimation for Gibbs distributions
• On the zeros of partition functions with multi-spin interactions

This page was built for publication: Approximate counting and sampling via local central limit theorems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083602)