Hafnians, perfect matchings and Gaussian matrices

DOI10.1214/15-AOP1036zbMATH Open1393.60009arXiv1409.3905OpenAlexW2482401181WikidataQ104523584 ScholiaQ104523584MaRDI QIDQ317488FDOQ317488

Ofer Zeitouni, Alex Samorodnitsky, Mark Rudelson

Publication date: 30 September 2016

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

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.

Full work available at URL: https://arxiv.org/abs/1409.3905

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The concentration of measure phenomenon
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• The complexity of computing the permanent
• Computing the Partition Function for Perfect Matchings in a Hypergraph
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• Permanents
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
• Approximating the Permanent
• The Littlewood-Offord problem and invertibility of random matrices
• Smallest singular value of a random rectangular matrix
• The local semicircle law for a general class of random matrices
• Concentration of the spectral measure for large matrices
• Concentration of permanent estimators for certain large matrices.
• Singular values of Gaussian matrices and permanent estimators
• Local semicircle law with imprimitive variance matrix
• Random weighting, asymptotic counting, and inverse isoperimetry

Cited In (7)

• 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
• Spectral Analysis of Matrix Scaling and Operator Scaling
• Nonnegativity for hafnians of certain matrices
• The Hafnian master theorem
• Approximating permanents and hafnians
• A novel approach to perturbative calculations for a large class of interacting boson theories

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)