Diffuse Gaussian Truncation For Deterministic Approximate Counting

Abstract

We give deterministic FPTASes for two dense counting problems on which the known deterministic algorithms, based on zero-free interpolation, run in quasipolynomial time. For fixed $0<\gamma<1/2$ and $0<\theta\leq1$, the first approximates $\mathrm{haf}(A)$ for a symmetric matrix $A$ when its support graph $G$ has minimum degree at least $(1/2+\gamma)n$ and its nonzero entries lie in $[\theta,1]$. It also approximates permanents under the analogous bipartite condition, including full-support matrices in $[\theta,1]$. For fixed $\beta>0$ and $0<\kappa\leq1$, the second approximates the zero-field Ising partition function $Z(J)$ for zero-diagonal real symmetric matrices $J$ satisfying $\max_{i,j}|J_{ij}|\leq\beta/n$ and $\lambda_{\max}(J)\leq1-\kappa$. No separate lower-eigenvalue condition is imposed. We further prove $\log\mathrm{haf}(A)=h_A(G)-n/2+O_{\gamma,\theta}(1)$ and $Z(J)=2^n\det(I-J)^{-1/2}(1+O_{\beta,\kappa}(1/n))$. Here $h_A(G)$ is the maximum weighted fractional-matching entropy. For unweighted graphs, the first formula improves the Cuckler--Kahn error from $o(n)$ to $O_\gamma(1)$ on the fixed-margin class and extends it to weights in $[\theta,1]$. Both algorithms use a common Gaussian truncation principle. Each problem becomes an integral of a product of a fixed entire function over Gaussian coordinates, with possibly indefinite moment matrix entries of order $1/n$. Cancelling the linear term and exactly resumming the quadratic term leaves a coordinate remainder vanishing to order at least three. Complex dilation handles small supports. For large supports, we bound the recombined tail by a large-deviation rate that beats the entropy of the subsets. The truncation error is at most $(CR/n)^{R/2}+e^{-cn}$. This faster-than-geometric decay permits $R\log(en/R)=O(\log n+\log(1/\epsilon))$ and hence polynomial enumeration.