Stability and complexity of mixed discriminants

2018/06/13 by Barvinok, Alexander · 1 citation
#15A15 #15B48 #41A10 #68W25 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA)

paper · doi:10.48550/arxiv.1806.05105

Abstract

We show that the mixed discriminant of n positive semidefinite n × n real symmetric matrices can be approximated within a relative error ε>0 in quasi-polynomial n^{O(ln n -ln ε)} time, provided the distance of each matrix to the identity matrix in the operator norm does not exceed some absolute constant γ₀ >0. We deduce a similar result for the mixed discriminant of doubly stochastic n-tuples of matrices from the Marcus - Spielman - Srivastava bound on the roots of the mixed characteristic polynomial. Finally, we construct a quasi-polynomial algorithm for approximating the sum of m-th powers of principal minors of a matrix, provided the operator norm of the matrix is strictly less than 1. As is shown by Gurvits, for m=2 the problem is #P-hard and covers the problem of computing the mixed discriminant of positive semidefinite matrices of rank 2.

Cited by

• Subtleties of non-Abelian D-brane actions and their effect on holographic heavy-light meson spectra

Related

• Concentration of the mixed discriminant of well-conditioned matrices
• A simple polynomial time algorithm to approximate the permanent within a simply exponential factor
• Computational complexity of decomposing a symmetric matrix as a sum of positive semidefinite and diagonal matrices
• A characterization of the mixed discriminant
• Average-case matrix discrepancy: satisfiability bounds