Hafnians, perfect matchings and Gaussian matrices

• Mark Rudelson ^[3] ; Alex Samorodnitsky ^[1] ; Ofer Zeitouni ^[2]
  1. [1] Hebrew University of Jerusalem

     Hebrew University of Jerusalem

     Israel

     
  2. [2] New York University

     New York University

     Estados Unidos

     
  3. [3] University of Michigan–Ann Arbor

     University of Michigan–Ann Arbor

     City of Ann Arbor, Estados Unidos

     

  Mostrar afiliaciones +
• Localización: Annals of probability: An official journal of the Institute of Mathematical Statistics, ISSN 0091-1798, Vol. 44, Nº. 4, 2016, págs. 2858-2888
• Idioma: inglés
• DOI: 10.1214/15-AOP1036
• Enlaces
  • Texto completo
• Resumen

  • 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.