PaperlayerView exact revision on arXiv

Source-linked AI summary

Diffuse Gaussian Truncation For Deterministic Approximate Counting

Zihong Yi

arXiv:2609.04079v1cs.DSmath.COmath.PR

TL;DR

The paper addresses dense counting problems whose known deterministic approximation algorithms remain quasipolynomial. It develops a Gaussian truncation approach yielding deterministic FPTASes for dense matchings and full-support weighted hafnians or permanents, together with a diffuse zero-field Ising result.

  • Problem

    Known deterministic approximation algorithms for the permanent and Ising partition function on the considered dense inputs remain quasipolynomial.

  • Method

    The approach uses Gaussian products with diffuse moment matrices, exactly resums linear and quadratic contributions, and truncates the resulting coordinate expansion.

  • Results

    The paper gives deterministic FPTASes for unweighted perfect matchings in the corresponding dense graph classes and for full-support hafnians and permanents with entries in [θ, 1].

  • Takeaways & Limitations

    The method yields polynomially many retained terms because the recombined tail decays faster than geometrically and the large-support rate beats subset entropy.

  • Takeaways & Limitations

    The Ising algorithm assumes rational input matrices, while its spectral condition is one-sided and does not require a lower-eigenvalue bound.

Abstract

from arXiv · show

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<θ\leq1$, the first approximates $\mathrm{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<κ\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β/n$ and $λ_{\max}(J)\leq1-κ$. No separate lower-eigenvalue condition is imposed. We further prove $\log\mathrm{haf}(A)=h_A(G)-n/2+O_{γ,θ}(1)$ and $Z(J)=2^n\det(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 $R\log(en/R)=O(\log n+\log(1/ε))$ and hence polynomial enumeration.

1. Introduction

The paper develops deterministic FPTASes for dense weighted matchings, permanents, and diffuse zero-field Ising models, replacing quasipolynomial interpolation with Gaussian truncation. It also gives constant-error entropy and determinant formulas under the stated density, weight, and spectral conditions.

  • Scope and motivation: The paper targets dense hafnians and permanents, where known deterministic approximation algorithms remain quasipolynomial.The matching support must have minimum degree above the Dirac threshold, while permanent inputs satisfy the analogous bipartite condition.
  • Proof framework: The common proof framework reduces both problems to Gaussian products and uses entropy scaling, inverse-Gamma averaging, or Hubbard–Stratonovich reduction before truncation.The same framework also yields the Ising determinant approximation stated in the paper.
  • Main algorithms: A deterministic FPTAS applies to hafnians of dense weighted graphs and permanents under fixed positive weight and density margins.The running-time exponents may depend on the fixed parameters γ and θ.
  • Consequences: Full-support matrices with entries in [θ,1] admit deterministic FPTASes for both hafnians and permanents, while odd-order graphs admit near-perfect matching approximation.The near-perfect matching result assumes minimum degree at least (1/2+γ)|V(G)|.
  • Consequences: The weighted hafnian satisfies log haf(A) = h_A(G) − n/2 + O_γ,θ(1), improving the fixed-margin unweighted error from o(n) to O_γ(1).The formula extends to weights in a fixed positive interval.

1. Entropy and the inverse-Gamma reduction.

The matching reduction uses maximum-entropy scaling to normalize the dominant contribution, then represents the remaining hafnian ratio through Gaussian products and an inverse-Gamma parameter. A related symmetric-dilation construction handles permanents.

  • Matching reduction: Maximum-entropy scaling factors the optimizer as w*uv = auv r_u r_v, allowing the main exponential contribution to be separated from the residual ratio.Every perfect matching uses each vertex factor once.
  • Matching reduction: After normalization, the matching problem reduces to Q_E = haf(P_0 + E)/haf(P_0), where E is diffuse and has a fixed spectral margin.The normalized matrix X is stochastic and E1 = 0.
  • Inverse-Gamma reduction: Expanding by selected edges leaves coefficients represented as negative moments of a Gamma variable concentrated near its mode 1.The auxiliary variable has shape (n+1)/2 and rate (n−1)/2.
  • Permanent reduction: The bipartite permanent argument applies the same construction after symmetric dilation, using a complete-bipartite reference and modified Gamma parameters.This transfers the matching reduction to the permanent setting.

2. The Hubbard–Stratonovich reduction.

The Ising reduction uses the Hubbard–Stratonovich identity to eliminate the spin sum and obtain a Gaussian product directly. Unlike the matching reduction, it needs neither entropy scaling nor an auxiliary Gamma average.

  • Gaussian reduction: The Ising reduction reaches a Gaussian product directly, without entropy scaling or an auxiliary Gamma average.The resulting expression still requires quadratic resummation before the common truncation theorem applies.

3. Quadratic resummation.

Quadratic resummation cancels the linear term and absorbs the quadratic term into the Gaussian density, leaving higher-order coordinate remainders. Complex dilation controls small supports, while recombined large-support estimates control the remaining tail.

  • Quadratic resummation: Removing the linear and quadratic Taylor terms leaves coordinate factors vanishing to order three for matchings and four for Ising.The resulting factors are g_pm(z)−1 = O(z^3) and g_Is(z)−1 = −z^4/12 + O(z^6).
  • Truncation theorem: The common truncation theorem gives an error bounded by a rapidly decaying coordinate term plus an exponentially small term, uniformly for 2 ≤ R ≤ cn.It does not require positive semidefiniteness, one-sign coefficients, or a zero-free polynomial.
  • Small supports: For small coordinate sets, complex dilation and the maximum-modulus principle yield a layer bound of (C(s/n)^α)^s.Here α = ℓ/2−1 > 0 when the coordinate remainder vanishes to order ℓ.
  • Large supports: For large supports, the proof recombines terms before taking absolute values and separates few-large-coordinate and many-large-coordinate Gaussian events.The quadratic envelope remains integrable because of the spectral margin.
  • Large supports: A witness-set estimate gives an exp(−a√r n) cost, which beats the witness-set entropy ρ log(1/ρ) for r = ρn.This is why the proof needs principal-submatrix information and the entrywise diffuseness condition, not only a global spectral bound.
  • Coefficient computation: Inclusion–exclusion computes each retained coefficient through vertex deletion for matchings or explicit spin sums for Ising, at cost 3^|S| poly(|S|).Balancing the cutoff gives R log(en/R)=O(log n+log(1/ε)), enabling polynomial enumeration.

5. Evaluating retained subsets.

The cutoff is chosen as the least integer satisfying the truncation-error condition, balancing accuracy against subset-enumeration cost.

  • The least valid cutoff R satisfies R = O(b + log n).The bound depends only on the fixed truncation parameters, with b governing the target accuracy.
  • Choosing the least valid R avoids paying for an unnecessarily large retained expansion.The cutoff is selected by the first integer meeting the required error threshold.
  • The cutoff condition is designed to convert truncation accuracy into manageable retained-subset evaluation.This choice is the basis for the algorithmic enumeration bound developed next.

6. From truncation to an FPTAS.

The adaptive cutoff makes the truncation scheme polynomial-time, while the paper applies it to dense matching, permanent, and Ising problems within stated scope boundaries.

  • 6. From truncation to an FPTAS.: R log(en/R) = O(b + log n), so retained-term enumeration costs n^O(1)2^O(b).This least-cutoff balance avoids the quasipolynomial cost n^O(log(1/ε)) of taking R proportional to b.
  • 6. From truncation to an FPTAS.: The resulting deterministic schemes cover dense weighted matchings, permanents, and diffuse zero-field Ising models.The paper positions these applications against prior deterministic methods with broader or different scopes.
  • 6. From truncation to an FPTAS.: The matching asymptotics improve the fixed-margin unweighted remainder from o(n) to Oγ(1) and extend the formula to weights in a fixed positive interval.This comparison is stated for the fixed-margin class.
  • 6. From truncation to an FPTAS.: The Ising result uses a one-sided spectral condition and permits negative eigenvalues whose magnitude exceeds one.The entrywise diffuseness condition remains a separate hypothesis.
  • 6. From truncation to an FPTAS.: The paper defers scaling, analytic, and bit-complexity estimates to appendices and discusses method limitations and open problems separately.The stated organization separates the common truncation theorem, applications, and deferred technical details.

2. A truncation principle for diffuse Gaussian products

The common principle rewrites both applications as entire-function Gaussian products with diffuse, possibly indefinite moments, then exploits cancellation and spectral control to truncate them.

  • 2. A truncation principle for diffuse Gaussian products: Both applications produce the same analytic object: an expectation of a product of entire scalar factors under a Gaussian moment matrix.The moment matrix may be indefinite, so the Gaussian coordinates can be complex while Wick expansions remain available.
  • 2. A truncation principle for diffuse Gaussian products: Exact cancellation of the linear term and resummation of the quadratic term leave a coordinate remainder vanishing to order at least three.The admissible scalar factor formalizes this local vanishing condition.
  • 2. A truncation principle for diffuse Gaussian products: The envelope matrix and spectral margin provide integrable control even when the moment matrix is not positive semidefinite.The spectral condition is one-sided when one envelope weight is zero.
  • 2. A truncation principle for diffuse Gaussian products: Complex Gaussian marginalization transfers the full representation to principal coordinate subsets through analytic continuation.A common holomorphic neighborhood and Wick-rule agreement identify the two Gaussian representations.
  • 2. A truncation principle for diffuse Gaussian products: For small supports, complex dilation converts the local vanishing order and O(1/n) moments into strong support-size suppression.The resulting estimate is governed by a factor of the form (s/n)^(ℓs/2), with a stronger bound for singletons.
  • 2. A truncation principle for diffuse Gaussian products: Large-support control uses a witness-set large-deviation rate e^(-c√ρ n), which beats the subset entropy near small ρ.The square-root rate is stronger than the ordinary linear rate needed to overcome h2(ρ).

S CS and CSCT

The large-support analysis recombines the signed tail before taking absolute values, obtaining uniform exponential control and a cutoff that yields polynomial-time enumeration.

  • S CS and CSCT: The Gaussian tail contributes a rate exp{-dδ^2√r n/(4β) + C√n}, while subset counts are bounded through binary-entropy estimates.The parameter choices make the combined exponents strictly negative uniformly over admissible matrix sequences.
  • S CS and CSCT: The resulting truncation theorem applies uniformly to admissible scalar factors and matrices, with absolute convergence of the relevant expectations.The proof handles the β = 0 case separately, where all nonempty contributions vanish.
  • S CS and CSCT: The recombined large-support tail is controlled after preserving cancellation among all subsets beyond a linear cutoff.Taking absolute values earlier would destroy the cancellation needed for the tail estimate.
  • S CS and CSCT: Intermediate layers form a geometric series bounded by 2Λ_R, and the signed linear tail controls the remaining omitted subsets.The two estimates together yield the final truncation bound after splitting at the linear cutoff.
  • S CS and CSCT: The least cutoff satisfying the error condition obeys R = O(b + log n).This calculus fact prevents the retained expansion from acquiring a quasipolynomial dependence on the target accuracy.

3. Perfect matchings in dense graphs

The section develops deterministic FPTAS criteria for dense symmetric and bipartite matching instances by entropy scaling them to diffuse perturbations, then applying Gaussian and inverse-Gamma evaluations. It derives entropy normalizations, spectral and factor bounds, and polynomial-time approximation and existence consequences.

  • Matrix theorem: A diffuse centered perturbation of either symmetric reference matrix admits a deterministic relative approximation.Theorem 3.1 supplies the matrix-level approximation framework for the normalized hafnian.
  • Symmetric scaling: The symmetric scaling criterion requires factor bounds and spectral expansion conditions, yielding deterministic FPTASs with parameter-dependent polynomial running time.The criterion uses bounds on scaling factors, λ2(LG), and QG; dense regular spectral expanders satisfy the resulting algorithmic conditions.
  • Dense support consequences: Degree and codegree hypotheses give further FPTASs for dense supports, including random Bernoulli supports with probability tending to one.The graph and bipartite criteria cover dense supports with degree and codegree bounds and include corresponding Erdős–Rényi or Bernoulli instances.
  • Existence: For dense graphs above the fixed degree margin, every edge extends to a perfect matching and sufficiently large instances contain a perfect matching.The exact normalization and positivity arguments establish these existence properties for the relevant supports.
  • Entropy normalization: Dense weighted matching and permanent instances reduce to entropy factors times normalized hafnians or permanents of scaled matrices.The symmetric and bipartite entropy identities are haf(A) = e^hA(G) haf(X) and per(B) = e^hB per(Y*).
  • Evaluation and error control: The inverse-Gamma representation and cubic remainder enable fixed-subset evaluation and polynomial-time approximation of the normalized hafnian.The normalized hafnian is represented as an expectation, the scalar remainder satisfies f(z) = O(z^3), and truncation, tail, and quadrature errors are controlled.

4. The zero-field Ising model with diffuse couplings

The Ising application converts the zero-field partition function into a completed Gaussian product whose diffuse, spectrally controlled remainder can be truncated and evaluated deterministically. This yields a deterministic FPTAS and the approximation Z(J)=2^n det(I-J)^-1/2(1+O_{β,κ}(1/n)).

  • Representation: The Hubbard–Stratonovich identity converts the zero-field spin sum into a Gaussian product, and quadratic completion produces the common form used by the truncation theorem.Unlike matchings, this route needs neither entropy scaling nor an auxiliary Gamma average.
  • Representation: The Ising factor gIs(z)=e^-z^2/2 cosh z has remainder fIs(z)=gIs(z)-1 vanishing to order 4.Its admissibility uses envelope weights aR=0 and aI=1/2, with Cf=1/8 and δf=1/2.
  • Matrix control: The completed matrix K=J(I-J)^-1 retains diffuse entrywise scale and the spectral margin required for Gaussian integrability.Its negative eigenvalues lie in [-β/(1+β),0], while the entrywise and spectral controls depend only on β and κ.
  • Approximation: ZK=1+O_{β,κ}(1/n), so Z(J)=2^n det(I-J)^-1/2(1+O_{β,κ}(1/n)).The determinant estimate follows from the eigenvalues of J and the zero-diagonal condition.
  • Algorithm: Retained subset terms are positive and computable by summing over 2^|T| spin configurations, with each coefficient costing 3^|S| poly(|S|) arithmetic operations.The truncation chooses R so that the retained sum achieves the requested accuracy while remaining polynomially enumerable.
  • Algorithm: The resulting deterministic algorithm has polynomial bit complexity in the input length and accuracy parameter for fixed β and κ.Small instances or large requested precision are handled by direct enumeration; otherwise the truncated expansion is evaluated with controlled error.

5. Scope and open problems

The method’s main scope boundary is diffuseness: entrywise O(1/n) control is essential to the truncation argument and is not supplied by a spectral margin alone. The paper identifies sparse expanders and surviving finite-rank modes as unresolved extensions.

  • Method boundary: Entrywise O(1/n) control is intrinsic to the truncation argument and is not implied by the spectral margin.This prevents direct application to sparse expanders, which would require graph-specific resummation or correlation estimates.
  • Open extensions: The applications eliminate a linear mode through E1=0 for matchings and zero external field for Ising.Whether a surviving finite-rank mode can be integrated separately remains open because uniform envelope and evaluation bounds are unavailable.

1. The truncation principle.

At the exact graph Dirac threshold, entropy scaling can assign order-one weight to a single edge, so the present method does not reach that endpoint. The paper leaves deterministic FPTAS existence for all Dirac graphs open there.

  • Endpoint limitation: The present method does not reach the exact graph Dirac threshold because entropy scaling may place order-one weight on an edge.A separate construction shows the smallest scaled eigenvalue can approach -1, and deterministic FPTAS existence at the endpoint remains open.

2. Perfect matchings.

The matching results leave several boundaries open: the endpoint spectral behavior, weighted pseudorandom supports below half degree, sampling, and non-diffuse Ising-style remainders. A structured endpoint family remains tractable by specialized matching-count methods.

  • Endpoint family: A structured endpoint family with one bounded-degree replacement graph admits a deterministic FPTAS through a matching-size expansion and specialized approximation or dynamic programming.When the maximum matching is small, the sum is evaluated exactly in 2^O(μ) poly(m)=poly(m,1/ε) time.
  • Degree boundary: Below the half-degree threshold, the unweighted pseudorandom result has no fully analogous weighted statement in the full degree–codegree range.The weighted extension remains open in that regime.
  • Sampling: The counting algorithm does not immediately yield a sampler because conditioning on k matching edges reduces the guaranteed degree surplus from γn to γn-k.This loss of degree surplus is the stated obstruction to direct sampling.

3. The Ising model.

The Ising approximation has two explicit scope boundaries: it does not cover deterministic approximation under a spectral hypothesis alone or the n^-1/2 interaction scale of dense spin glasses.

  • The 1 + O(1/n) conclusion fails without the entrywise hypothesis, and deterministic approximation under a spectral hypothesis alone remains open.
  • The argument does not reach the n^-1/2 interaction scale of dense spin glasses because the effective entrywise parameter grows like √n and the small-support bound no longer survives summation over supports.

Appendix A. Proofs of the scaling-criterion consequences

The appendix derives scaling, factor, spectral, and algorithmic consequences for dense matching and permanent instances, then verifies the analytic remainder and bit-complexity bounds used by the algorithms.

  • Scaling and normalization: Stochastic normalization handles regular cases, while Sinkhorn scaling handles bipartite instances with total support.
  • Spectral consequences: The codegree and Laplacian estimates establish a fixed singular-value or spectral gap, verifying the hypotheses needed for the approximation theorems.
  • Random instances: For random bipartite matrices, Chernoff and Hall estimates show the required degree, codegree, and total-support properties with probability 1 − o(1).
  • Scaling and normalization: Dense support and degree conditions yield bounded scaling factors and uniform supported-entry weights depending only on γ and θ.
  • Analytic and computational bounds: Quadratic resummation leaves remainders vanishing to order three for matchings and four for Ising, while elementary terms and prefactors are evaluable in polynomial time per term.
Loading 2609.04079v1…