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<γ<1/2 and 0<θ≤1, the first approximates haf(A) for a symmetric matrix A when its support graph G has minimum degree at least (1/2+γ)n and its nonzero entries lie in [θ,1]. It also approximates permanents under the analogous bipartite condition, including full-support matrices in [θ,1]. For fixed β>0 and 0<κ≤1, the second approximates the zero-field Ising partition function Z(J) for zero-diagonal real symmetric matrices J satisfying maxi,j|Jij|≤β/n and λmax(J)≤1−κ. No separate lower-eigenvalue condition is imposed. We further prove loghaf(A)=hA(G)−n/2+Oγ,θ(1) and Z(J)=2ndet(I−J)−1/2(1+Oβ,κ(1/n)). Here hA(G) is the maximum weighted fractional-matching entropy. For unweighted graphs, the first formula improves the Cuckler--Kahn error from o(n) to Oγ(1) on the fixed-margin class and extends it to weights in [θ,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 Rlog(en/R)=O(log n+log(1/ε)) and hence polynomial enumeration.
Related
- Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs
- Balanced truncation for bilinear time-delay systems with approximate Gramians
- Log-concavity and Approximate Counting for Totally Unimodular Polytopes
- Approximate Counting for Mixed p-Spin Glasses in Weak External Fields via Cluster Expansion
- Rate-Distortion-Perception Tradeoff for Vector Gaussian Sources with Limited Common Randomness: Exact Characterization and Approximate Universality
BibTeX
@misc{yi2026diffuse,
title = {{Diffuse Gaussian Truncation For Deterministic Approximate Counting}},
author = {Zihong Yi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04079},
eprint = {2609.04079},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04079},
}
RIS
TY - UNPB
TI - Diffuse Gaussian Truncation For Deterministic Approximate Counting
AU - Zihong Yi
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.04079
UR - https://arxiv.org/abs/2609.04079
AB - 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<γ<1/2 and 0<θ≤1, the first approximates haf(A) for a symmetric matrix A when its support graph G has minimum degree at least (1/2+γ)n and its nonzero entries lie in [θ,1]. It also approximates permanents under the analogous bipartite condition, including full-support matrices in [θ,1]. For fixed β>0 and 0<κ≤1, the second approximates the zero-field Ising partition function Z(J) for zero-diagonal real symmetric matrices J satisfying max_i,j|J_ij|≤β/n and λ_max(J)≤1−κ. No separate lower-eigenvalue condition is imposed. We further prove loghaf(A)=h_A(G)−n/2+O_γ,θ(1) and Z(J)=2^ndet(I−J)^−1/2(1+O_β,κ(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_γ(1) on the fixed-margin class and extends it to weights in [θ,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 Rlog(en/R)=O(log n+log(1/ε)) and hence polynomial enumeration.
ER -