Hafnians, perfect matchings and Gaussian matrices

DOI10.1214/15-AOP1036zbMath1393.60009arXiv1409.3905OpenAlexW2482401181WikidataQ104523584 ScholiaQ104523584MaRDI QIDQ317488

Ofer Zeitouni, Alex Samorodnitsky, M. V. Rudel'son

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

zbMATH Keywords

perfect matchinghafnianrandom Gaussian matrices

Mathematics Subject Classification ID

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

Related Items

The Hafnian master theorem, A novel approach to perturbative calculations for a large class of interacting boson theories, Generating functions and counting formulas for spanning trees and forests in hypergraphs, Approximating permanents and hafnians, On moments of Brownian functionals and their interpretation in terms of random walks, Spectral Analysis of Matrix Scaling and Operator Scaling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The local semicircle law for a general class of random matrices
• The complexity of computing the permanent
• Local semicircle law with imprimitive variance matrix
• Random weighting, asymptotic counting, and inverse isoperimetry
• Concentration of the spectral measure for large matrices
• Concentration of permanent estimators for certain large matrices.
• The Littlewood-Offord problem and invertibility of random matrices
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Computing the Partition Function for Perfect Matchings in a Hypergraph
• Approximating the Permanent
• Singular values of Gaussian matrices and permanent estimators
• Smallest singular value of a random rectangular matrix
• 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