Random Gaussian matrices and Hafnian estimators

We analyze the behavior of the Barvinok estimator of the hafnian of even dimension, symmetric matrices with non negative entries. We introduce a condition under which the Barvinok estimator achieves sub-exponential 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.

• Publication year

  2014

• Venue

  arXiv.org

• Publication date

  2014-09-12

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1214/15-AOP1036arXiv 1409.3905
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Singular values of Gaussian matrices and permanent estimators

  2013influential reference
• Local semicircle law with imprimitive variance matrix

  2013cited by this paper
• The local semicircle law for a general class of random matrices

  2012cited by this paper
• Computing the Partition Function for Perfect Matchings in a Hypergraph

  2010cited by this paper
• The smallest singular value of a random rectangular matrix

  2008cited by this paper
• The Littlewood-Offord problem and invertibility of random matrices

  2007cited by this paper
• Matching polynomial of graph

  2007cited by this paper
• Simple deterministic approximation algorithms for counting matchings

  2007cited by this paper
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries

  2004cited by this paper
• Concentration of permanent estimators for certain large matrices

  2004cited by this paper
• Random weighting, asymptotic counting, and inverse isoperimetry

  2003cited by this paper
• A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

  2001cited by this paper
• The concentration of measure phenomenon

  2001cited by this paper
• CONCENTRATION OF THE SPECTRAL MEASURE FOR LARGE MATRICES

  2000cited by this paper
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor

  1999influential reference
• A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents

  1998cited by this paper
• Spaces with large distance to l∞n and random matrices

  1990cited by this paper
• Approximating the Permanent

  1989cited by this paper
• The Complexity of Computing the Permanent

  1979cited by this paper

• Employing Integrated Quantum Photonic Computers for Gaussian Boson Sampling

  2024cites this paper
• Generating functions and counting formulas for spanning trees and forests in hypergraphs

  2024cites this paper
• Flexible ansatz for N-body configuration interaction

  2021cites this paper
• The boundary for quantum advantage in Gaussian boson sampling

  2021cites this paper
• Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs

  2021cites this paper
• Measuring the similarity of graphs with a Gaussian boson sampler

  2020cites this paper
• Simulability of partially distinguishable superposition and Gaussian boson sampling

  2020cites this paper
• On moments of Brownian functionals and their interpretation in terms of random walks

  2020cites this paper
• A quantum hardware-induced graph kernel based on Gaussian Boson Sampling

  2019cites this paper
• Exact simulation of Gaussian boson sampling in polynomial space and exponential time

  2019cites this paper
• Spectral Analysis of Matrix Scaling and Operator Scaling

  2019cites this paper
• A faster hafnian formula for complex matrices and its benchmarking on the Titan supercomputer

  2018cites this paper
• A Faster Hafnian Formula for Complex Matrices and Its Benchmarking on a Supercomputer

  2018cites this paper
• Using Gaussian Boson Sampling to Find Dense Subgraphs.

  2018cites this paper
• A novel approach to perturbative calculations for a large class of interacting boson theories

  2017cites this paper
• Gaussian boson sampling for perfect matchings of arbitrary graphs

  2017cites this paper
• Approximating permanents and hafnians

  2016cites this paper