Hafnians, perfect matchings and Gaussian matrices

DOI10.1214/15-AOP1036MaRDI QIDQ317488zbMATH OpenOpenAlexWikidataFDO

Authors Alex Samorodnitsky, Ofer Zeitouni, Mark Rudelson

Publication date 30 September 2016

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.3905, https://projecteuclid.org/euclid.aop/1470139156

zbMATH Keywords

perfect matchinghafnianrandom Gaussian matrices

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We analyze the behavior of the Barvinok estimator of the hafnian of even dimension, symmetric matrices with nonnegative entries. We introduce a condition under which the Barvinok estimator achieves subexponential errors, and show that this condition is almost optimal. Using that hafnians count the number of perfect matchings in graphs, we conclude that Barvinok's estimator gives a polynomial-time algorithm for the approximate (up to subexponential errors) evaluation of the number of perfect matchings.

Recommendations

• A determinant-based algorithm for counting perfect matchings in a general graph
• Nonnegativity for hafnians of certain matrices
• Approximating permanents and hafnians
• Counting perfect matchings as fast as Ryser
• Singular values of Gaussian matrices and permanent estimators

Cites work

• scientific article; zbMATH DE number 5485444 (Why is no real title available?)
• scientific article; zbMATH DE number 3458807 (Why is no real title available?)
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Approximating the Permanent
• Computing the partition function for perfect matchings in a hypergraph
• Concentration of permanent estimators for certain large matrices.
• Concentration of the spectral measure for large matrices
• Local semicircle law with imprimitive variance matrix
• Permanents
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• Random weighting, asymptotic counting, and inverse isoperimetry
• Singular values of Gaussian matrices and permanent estimators
• Smallest singular value of a random rectangular matrix
• The Littlewood-Offord problem and invertibility of random matrices
• The complexity of computing the permanent
• The concentration of measure phenomenon
• The local semicircle law for a general class of random matrices

Cited in

(10)

• Generating functions and counting formulas for spanning trees and forests in hypergraphs
• On moments of Brownian functionals and their interpretation in terms of random walks
• The Hafnian master theorem
• Spectral analysis of matrix scaling and operator scaling
• A novel approach to perturbative calculations for a large class of interacting boson theories
• The Hafnian of Toeplitz matrices of special type, perfect matchings and Bessel polynomials
• A computationally motivated definition of parametric estimation and its applications to the Gaussian distribution
• Nonnegativity for hafnians of certain matrices
• Approximating permanents and hafnians
• Singular values of Gaussian matrices and permanent estimators

This page was built for publication: Hafnians, perfect matchings and Gaussian matrices

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