PaperlayerView exact revision on arXiv

Source-linked AI summary

Subexponential Approximation of the Permanent in Deterministic Polynomial Time

Sergei Kudria, Jason Luo, Mahbod Majid

arXiv:2609.10516v1cs.DScs.CCmath.CO

TL;DR

Deterministic polynomial-time guarantees for arbitrary nonnegative rational matrices had remained exponential in n, with a deterministic FPTAS still open. The paper optimizes a matching-based upper bound and obtains a deterministic subexponential approximation, answering a question about the best possible exponential base.

  • Problem

    For arbitrary nonnegative rational matrices, deterministic polynomial-time guarantees had remained exponential in n, while a deterministic FPTAS remained open.

    Source: §1 · p. 3

  • Method

    The paper optimizes a permanent upper bound and uses a contracting deletion recursion to compute weighted matching probabilities.

    Source: §4.1 · p. 18, §6.1 · p. 24

  • Results

    The algorithm gives the first deterministic polynomial-time approximation within exp(o(n)) for arbitrary nonnegative rational matrices.

    Source: §1 · p. 4

  • Takeaways & Limitations

    The error per row tends to zero, so the infimum α > 1 permitting polynomial-time α^n approximation is 1.

    Source: §1 · p. 4

    The running-time bound does not guarantee polynomial time for the parameter choice λ = nc/2.

    Source: §2.2 · p. 7

Abstract

from arXiv · show

We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor. For a matrix of order $n$, the approximation factor is \[ \exp\!\left(O\!\left(\frac{n(\log\log n)^2}{\log n}\right)\right)=\exp(o(n)). \] All previously known deterministic polynomial time guarantees for unrestricted inputs had approximation factors $\exp(\Omega(n))$. Our proof uses convex optimization to tighten an upper bound on the permanent. The bound is based on weighted sums over all matchings in a bipartite graph representing the matrix, and correlations between unmatched vertices control its error. We approximate these sums deterministically using correlation decay and a bound on the effect of vertex deletion.

1 Introduction

The paper gives the first deterministic polynomial-time approximation of the permanent for arbitrary nonnegative rational matrices with a subexponential factor. It also presents parameterized and sparsity-dependent guarantees alongside the main result.

1 Introduction

  • Deterministic polynomial-time guarantees for unrestricted inputs had remained exponential in n, although a randomized FPTAS was known and a deterministic one remained open.Exact evaluation is #P-complete even for zero-one matrices.Source: §1 · p. 3
  • The algorithm achieves an exp(o(n)) approximation factor for arbitrary nonnegative rational matrices in deterministic polynomial time.The paper states this eventually improves on every fixed exponential factor c^n for c > 1.Source: §1 · p. 4
  • The main theorem uses bit operations polynomial in the input length, and a matching test detects whether the permanent is zero before approximation.The computational model measures input length by the binary description of the rational entries.Source: §1 · p. 4
  • The error per row, n^-1 log(U/L), tends to zero, answering the question of whether the infimum α > 1 for polynomial-time α^n approximation is 1.The paper states that this infimum is 1.Source: §1 · p. 4
  • The theorem offers a tradeoff: increasing λ reduces the first error term but increases the running-time bound, while η controls numerical error.For fixed λ and η, the running time is polynomial in input length; optimization, estimation, and rounding contribute at most 8ηn to logarithmic interval width.Source: §1 · p. 4
  • When every row and column has at most fixed degree Δ, the logarithmic width improves to O_Δ(n log log n / log n).The hidden multiplicative constant may depend on Δ, but not on n or the matrix entries.Source: §1 · pp. 4–5
  • A deterministic polynomial-time exp(O(n^(1−δ))) approximation would imply a deterministic FPTAS, but the paper's logarithmic saving does not yield one by this amplification.The implication also holds for zero-one matrices with at most three ones per row and column, yielding a deterministic FPTAS for general nonnegative rational matrices.Source: §1 · p. 5

2 Technical overview

The technical overview develops a permanent upper bound from weighted matchings and optimizes its edge weights. It explains how unmatched-vertex estimates, made tractable by correlation decay and deletion stability, support projected subgradient steps for finding those weights.

2.1 Constructing an upper bound by choosing edge weights

  • The matching partition function upper-bounds the permanent, and reweighting seeks to limit both the contribution of imperfect matchings and excess compensation for perfect ones.Taking logarithms makes the upper-bound objective convex, so minimizing it over edge weights searches for the best bound of this form.Source: §2.1 · pp. 5–6

2.2 The approximation theorem from two ingredients

  • Choosing Λ of order (log n)^2/(log log n)^4 yields polynomial running time and logarithmic approximation error O(n(log log n)^2/log n).The algorithm approximates log Z and edge-use probabilities under a per-vertex weight budget; increasing the budget improves the analytic bound but raises the running time.Source: §2.2 · p. 7

2.3 Bounding the approximation error using unmatched rows

  • The expected number of unmatched rows at optimal weights controls how quickly the optimized upper bound can decrease as the log budget grows.The proof relates unmatched-vertex probabilities to edge weights using a completion argument and positive correlation between the events that two endpoints are unmatched.Source: §2.3 · pp. 8–10

2.4 Counting through correlation decay

  • Deleting vertices gives recursions for unmatched probabilities and the partition function; truncating the resulting self-avoiding walk tree is effective because distant inputs have diminishing influence.The analysis adapts correlation-decay methods to unequal edge weights under the per-vertex budget constraint.Source: §2.4 · pp. 10–11
  • A coupling of matching distributions bounds deletion effects by at most 1 − qG(u) expected disagreements, and yields positive correlation of opposite-side unmatched events in bipartite graphs.The coupling is used only in the proof; the algorithm uses the resulting bound in its deterministic recursion, and the deletion bound also applies to general graphs.Source: §2.4 · p. 12
  • Deletion stability lets the correlation-decay recursion reuse stored estimates on small edges, so only large edges branch and the degree leaves the exponent.The recursion controls the error from forgotten deletions, with threshold κ of order ξ/Λ yielding O(ξ) error and polynomial branching in Λ and ξ^-1.Source: §2.4 · pp. 12–13

2.5 Finding the weights by subgradient steps

  • Projected subgradient steps using estimated edge probabilities find weights with objective within O(εn) of the optimum after O(mW^2/ε^2) steps.A bounded box contains a near-optimal point; rational, rounded directions keep encoding lengths polynomial, with relative probability error of order ε/W controlling objective error.Source: §2.5 · pp. 13–14

3 Related work

The section places this work alongside deterministic Bethe-permanent bounds and matching-counting algorithms. It distinguishes the paper's weighted all-matchings upper bound and correlation-based analysis from approaches that rely on Bethe bounds or graph expansion.

3 Related work

  • The Bethe permanent has a concave optimization formulation and graph-cover interpretation, and Anari and Rezaei show it approximates the permanent within a factor of 2n/2.Other guarantees rely on additional conditions: large girth for a sharp Bethe factor, or dense support and bounded positive weights for a deterministic FPTAS.Source: §3 · p. 14
  • Recent deterministic Bethe-bound improvements [Ana26] and [NP26] exploit nearly isolated weighted 2 × 2 blocks, whereas this paper optimizes an upper bound from matchings of every size and weight compensation.The paper uses correlations between unmatched vertices to bound the upper-bound error and a deletion bound to reuse computations on small edges.Source: §3 · pp. 14–15
  • Gamarnik and Katz use uniform large edge weights and graph expansion to control imperfect matchings, while this paper optimizes edge weights individually without assuming expansion.Their polynomial-time (1 + ε)n guarantee applies to zero-one matrices with bounded-degree bipartite graphs and fixed positive expansion.Source: §3 · p. 15
  • The matching-sum algorithm adapts recursive correlation-decay analysis to unequal edge weights and uses vertex deletion to control changes in unmatched probabilities.A coupling makes the differences between matchings before and after deletion follow a single path; the resulting bound supports computation reuse on small-weight edges.Source: §3 · p. 15
  • The paper's analytic contribution bounds the optimized upper-bound error using convexity, optimality conditions, and correlations between unmatched vertices.Its algorithmic contribution uses the deletion bound to reuse computations on small edges while keeping graph-size dependence polynomial.Source: §3 · p. 15

4 Preliminaries

The preliminaries establish matching-partition identities and deletion couplings, then use matching probabilities and convexity to support the paper’s optimization methods.

4.1 Matchings and their probabilities

  • The matching partition function and deletion recursion recover the partition function and edge probabilities from unmatched-vertex probabilities.The polytope of doubly stochastic matrices on the support is the convex hull of perfect-matching incidence matrices, and a maximum-cost assignment is computable in polynomial time.Source: §4.1 · p. 16
  • Deleting a vertex admits a coupling whose matchings differ along one alternating path, bounding changes in unmatched probabilities.On bipartite graphs, unmatched-vertex correlations are nonnegative across opposite sides and nonpositive on the same side.Source: §4.1 · pp. 17–18

4.2 Convex optimality and subgradient steps

  • The objective ΦA is convex, and a maximizing assignment together with edge probabilities supplies a subgradient for optimizing it.Projected subgradient steps average queried points; the section also gives an averaging bound for approximate directions.Source: §4.2 · pp. 19–20

5 The permanent approximation algorithm

The section gives a deterministic interval-approximation algorithm for the permanent and derives its polynomial-time subexponential guarantee by balancing accuracy against running time.

5 The permanent approximation algorithm

  • For rational matrices of total bit length S, the stated algorithm uses poly(S) bit operations.The section bounds the additional optimization work polynomially in the input length, λ, and η^-1, with absolute degree.Source: §5 · pp. 20, 22
  • A parameter choice yields polynomial time and logarithmic interval width O(n(log log n)^2/log n), giving an exp(O(n(log log n)^2/log n)) approximation factor.The proof chooses k so that k log^2 k = O(log n), keeping the exponential running-time factor polynomial.Source: §5 · p. 21
  • The algorithm optimizes a matching-based upper bound, then estimates the matching partition function and assignment term to construct rational endpoints.The objective combines log Z with the maximum compensation over perfect matchings; the section accounts for approximation errors from the input, optimization, and evaluation.Source: §5 · pp. 21–22

6 Optimizing the matching partition function

This section studies a convex matching-partition upper bound on the permanent, showing how its optimized value approaches the log permanent as the weight budget grows.

6 Optimizing the matching partition function

  • The matching-partition objective upper-bounds log per(A), and its optimized value tends to log per(A) as the budget parameter grows.The proof uses that Z(tA) has degree n in t and leading coefficient per(A).Source: §6 · p. 23

6.1 Removing the constraints by normalization

  • Normalization removes the weight constraints while preserving the minimum and joint convexity of the rescaled objective.At an optimizer, the expected number of unmatched rows bounds how quickly the optimized upper bound can decrease as the budget increases.Source: §6 · p. 23, §6.1 · pp. 24–25

7 Counting matchings under a fixed budget

The section gives a deterministic algorithm for estimating matching probabilities and the matching partition function under a vertex weight budget, using recursive correlation decay and deletion stability.

7 Counting matchings under a fixed budget

  • Theorem 7.1 returns relative-width ξ intervals for every edge probability and a width-ξn interval for log Z in deterministic time.Its runtime has absolute constants and polynomial degree; for fixed maximum support degree, the squared logarithm in the runtime bound can be replaced by a single logarithm.Source: §7 · p. 26
  • The algorithm approximates monomer probabilities by contracting the deletion recursion, then uses those estimates to compute edge probabilities and log Z.The recursion reuses stored probabilities on edges below a threshold; deletion stability controls the resulting error, while the threshold limits recursive children.Source: §7 · pp. 25–28
  • For fixed support degree, the probability-approximation recursion uses at most Δ children per step and achieves its accuracy with a single logarithm in the depth bound.The section contrasts this with the general-degree method, which uses thresholding and stored values for smaller edges.Source: §7 · pp. 26, 28

8 Optimization with normalized weights

Section 8 gives a procedure for finding positive rational weights that obey a per-vertex budget while keeping the normalized objective close to optimum.

8 Optimization with normalized weights

  • Projected subgradient averaging seeks near-optimal weights by normalizing edge weights, choosing directions from edge probabilities, and averaging iterates [Bub15, Section 3.1].Corollary 4.13 accounts for errors in the directions.Source: §8 · p. 28
  • For θ∈Q^E, λ≥1, and 0<ε≤1, the procedure returns positive rational weights with every vertex sum at most λ and objective at most OPT+εn.The objective guarantee is Φ_bA(log w)≤OPT_bA(log λ)+εn.Source: §8 · p. 29
  • The algorithm solves O(mW^2/ε^2) assignment problems and runs in time polynomial in the input and parameter encoding lengths and ε^-1.The returned weights, iterates, and inputs to Theorem 7.1 have polynomial encoding lengths.Source: §8 · p. 29
  • The optimization is restricted to a bounded box Q=[−W,0]^m that contains a point whose objective is close to the minimum.The analysis bounds the change in the objective when weights below a threshold are raised and then normalized.Source: §8 · pp. 29–31
  • Each approximate direction combines estimated edge probabilities with a maximum-weight assignment at costs θ−x, and its Euclidean norm is at most 2.The two component vectors have nonnegative entries summing to n.Source: §8 · p. 31

A Numerical details

The appendix establishes the numerical accuracy and running-time bounds used by the main algorithm.

A Numerical details

A.1 Directed evaluations and rational endpoints

Directed rational evaluations support the algorithm’s objective estimates and their required logarithmic accuracy.

A.1 Directed evaluations and rational endpoints

  • Logarithms, exponentials, and square roots can be bounded by rational endpoints within 2^-p using directed rounding in polynomial time.The running time is polynomial in input length, p, and output length.Source: §A.1 · p. 36
  • For positive binary rational inputs, |log A_e|=O(bits(A_e)); the estimate T and error bound E are each O(n).The rational outputs have encoding lengths polynomial in the input and parameter encoding lengths.Source: §A.1 · p. 36
  • An interval around y≥2^-K with width at most ζ2^-K-1 has endpoint logarithms within ζ, so O(K+log(1/ζ)) precision bits suffice.Applied to e^T and e^(T−E), this yields positive rational U,L with logarithmic bounds within 2ηn.Source: §A.1 · p. 36
  • The objective estimate uses an upper endpoint for log Z(w) and lower endpoints for log w_e in assignment costs, with tolerances chosen to keep additive error at most ηn.Theorem 7.1 supplies an interval of width O(ηn) containing log Z(w).Source: §A.1 · p. 36

A.2 Absorbing the box width’s dependence on n

The appendix bounds the box-width contribution so it can be absorbed into an absolute polynomial factor in n.

A.2 Absorbing the box width’s dependence on n

  • The inequality bounds t[b+log(z+e)]^2 by 2t[b+log t+1]^2+2z, absorbing z=log n into an absolute polynomial factor after exponentiation.Here λ, z=log n, and b=O(log(λ/η)); this proves (2) with an absolute polynomial degree.Source: §A.2 · p. 37

B Amplification to a relative approximation

A fixed power-saving deterministic polynomial-time approximation would yield a deterministic FPTAS by applying the algorithm to disjoint copies and taking roots. The paper's logarithmic saving does not meet that amplification condition, and the parameter choice needed for a fixed power saving incurs superpolynomial time.

B Amplification to a relative approximation

  • The paper's logarithmic saving does not become a relative approximation through polynomially many copies, even at fixed target accuracy.The amplification observation applies to a fixed power saving, not the present logarithmic saving.Source: B Amplification to a relative… · p. 37
  • A deterministic polynomial-time exp(O(N^(1−δ))) approximation for every nonnegative rational matrix would imply a deterministic FPTAS.The hypothesis requires fixed constants C and δ > 0; the FPTAS returns rational endpoints with relative error controlled by the requested accuracy.Source: B Amplification to a relative… · p. 37
  • Disjoint copies multiply the permanent, so taking the rth root of an interval for r copies reduces its logarithmic width by a factor of r.The argument uses closure under disjoint unions and multiplicativity; rational endpoints can be recovered in polynomial time.Source: B Amplification to a relative… · pp. 37–38
  • The rational-root step approximates each endpoint by bisection, with polynomially many steps and exact integer-power comparisons.For endpoint encoding length B and target α, the passage gives O(B + log(1/α)) bisection steps.Source: B Amplification to a relative… · p. 38
  • Choosing λ ≍ n^(2δ) and η ≍ n^(−δ) gives error O(n^(1−δ)), but the running time includes exp(O(n^δ log^2 n)).Thus this parameter choice does not provide the polynomial-time hypothesis required by the amplification theorem.Source: B Amplification to a relative… · p. 39

C The all-ones example

The all-ones matrix provides an explicit case for examining the optimized upper-bound objective. The stated limitation concerns that objective, even though the matrix's permanent is n!.

C The all-ones example

  • For the all-ones matrix, uniform logarithmic weights y_ij = log(Λ/n) attain OPT_A(log Λ).The passage states this for n ≥ 4 and Λ ≥ 1.Source: C The all-ones example · p. 39
  • Averaging feasible weights over row and column permutations gives constant coordinates without increasing the objective.Convexity and symmetry justify the averaging; among uniform weights, t = Λ/n minimizes the objective.Source: C The all-ones example · p. 39
  • The error limitation applies to the optimized objective even for the all-ones matrix, whose permanent is n!.The stated parameter range is 1 ≤ Λ ≤ n^2/16.Source: C The all-ones example · p. 39

D Reduction to zero-one matrices of degree at most three

The reduction converts nonnegative rational matrices into zero-one matrices with at most three ones per row and column while preserving the permanent up to a positive rational factor. It clears denominators, encodes integer weights with an unweighted graph, and then reduces degrees.

D Reduction to zero-one matrices of degree at most three

  • Every nonnegative rational matrix can be converted in polynomial time to a zero-one matrix of maximum row and column degree three, with per(Q) = c per(A).The multiplier c is a positive rational, and the resulting matrix has polynomial size.Source: D Reduction to zero-one matrices of… · p. 40
  • Clearing row denominators first produces integer weights and a positive integer scaling factor with polynomial encoding cost.The integer-weight and degree-reduction steps then preserve the scaled permanent.Source: D Reduction to zero-one matrices of… · p. 40
  • Integer edge weight k is encoded by an unweighted bipartite gadget with exactly k completions when the original edge is selected.The gadget uses a directed acyclic graph with exactly k source-to-sink paths and O(log k) vertices and edges; its size depends on binary weight length.Source: D Reduction to zero-one matrices of… · pp. 40–41
  • Degree reduction replaces each original vertex with a path gadget that forces exactly one incident original edge into every perfect matching.The construction yields maximum degree three and a weight-preserving bijection of perfect matchings; each side has 2m − n vertices.Source: D Reduction to zero-one matrices of… · pp. 40–41

Related papers

Loading 2609.10516v1…