Concentration of random determinants and permanent estimators

DOI10.1137/080733784zbMATH Open1200.15021arXiv0905.1909OpenAlexW2053695612MaRDI QIDQ3583307FDOQ3583307

Authors: Kevin P. Costello, Van Vu 

Publication date: 27 August 2010

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We show that the absolute value of the determinant of a matrix with random independent (but not necessarily iid) entries is strongly concentrated around its mean. As an application, we show that the Godsil-Gutman and Barvinok estimators for the permanent of a strictly positive matrix give sub-exponential approximation ratios with high probability.

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

Recommendations

• Concentration of permanent estimators for certain large matrices.
• The method of random determinants for estimating the permanent
• Singular values of Gaussian matrices and permanent estimators
• Approximating the permanent via nonabelian determinants
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.

zbMATH Keywords

random matrixsingular valuesdeterminantpermanent

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Combinatorial probability (60C05) Determinants, permanents, traces, other special matrix functions (15A15)

Cited In (9)

• From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices
• Singular values of Gaussian matrices and permanent estimators
• Random matrices: universality of local eigenvalue statistics
• Random doubly stochastic matrices: the circular law
• A general law of large permanent
• Computing the partition function for perfect matchings in a hypergraph
• Immanants of blocks from random matrices in some unitary ensembles
• Concentration of permanent estimators for certain large matrices.
• The logarithmic law of random determinant

This page was built for publication: Concentration of random determinants and permanent estimators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3583307)