Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Stability and complexity of mixed discriminants

Author: Alexander Barvinok
Journal: Math. Comp. 89 (2020), 717-735
MSC (2010): Primary 15A15, 15B48, 68W25, 41A10
Published electronically: August 27, 2019
MathSciNet review: 4044448
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: We show that the mixed discriminant of $ n$ positive semidefinite $ n \times n$ real symmetric matrices can be approximated within a relative error $ \epsilon >0$ in quasi-polynomial $ n^{O(\ln n -\ln \epsilon )}$ time, provided the distance of each matrix to the identity matrix in the operator norm does not exceed some absolute constant $ \gamma _0 >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 $ \nu $th powers of principal minors of a matrix, for an integer $ \nu \geq 1$, provided the operator norm of the matrix is strictly less than 1. As is shown by Gurvits, for $ \nu =2$ the problem is $ \char93 P$-hard and covers the problem of computing the mixed discriminant of positive semidefinite matrices of rank 2.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 15A15, 15B48, 68W25, 41A10

Retrieve articles in all journals with MSC (2010): 15A15, 15B48, 68W25, 41A10

Additional Information

Alexander Barvinok
Affiliation: Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1043

Keywords: Mixed discriminant, mixed characteristic polynomial, algorithm, approximation, complex zeros
Received by editor(s): November 26, 2018
Received by editor(s) in revised form: April 17, 2019, and May 26, 2019
Published electronically: August 27, 2019
Additional Notes: This research was partially supported by NSF grants DMS 1361541 and DMS 1855428
Article copyright: © Copyright 2019 American Mathematical Society