HAFNIANS, PERFECT MATCHINGS AND GAUSSIAN MATRICES

• 成果类型: Article
• 署名作者: Rudelson, Mark; Samorodnitsky, Alex; Zeitouni, Ofer
• 署名单位: University of Michigan System; University of Michigan; Hebrew University of Jerusalem; Weizmann Institute of Science; New York University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/15-AOP1036
• 发表日期: 2016
• 页码: 2858-2888
• 关键词: algorithm; permanent

摘要

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.