Stability and complexity of mixed discriminants

DOI10.1090/MCOM/3468MaRDI QIDQ5207439zbMATH OpenOpenAlexWikidataFDO

Authors Alexander Barvinok

Publication date 27 December 2019

Published in Mathematics of Computation (Search for Journal in Brave)

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

zbMATH Keywords

algorithmapproximationcomplex zerosmixed discriminantmixed characteristic polynomial

Mathematics Subject Classification ID

Approximation algorithms (68W25) Determinants, permanents, traces, other special matrix functions (15A15) Miscellaneous inequalities involving matrices (15A45) Quadratic and bilinear forms, inner products (15A63)

Abstract: We show that the mixed discriminant of $n$ positive semidefinite $nimesn$ real symmetric matrices can be approximated within a relative error $epsilon>0$ in quasi-polynomial $n^{O(lnn-lnepsilon)}$ time, provided the distance of each matrix to the identity matrix in the operator norm does not exceed some absolute constant $gamm{a}_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 $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 $$-hard and covers the problem of computing the mixed discriminant of positive semidefinite matrices of rank 2.

Recommendations

• Mathematical Foundations of Computer Science 2005
• A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume
• Computing mixed discriminants, mixed volumes, and permanents
• Concentration of the mixed discriminant of well-conditioned matrices
• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary

Cites work

• scientific article; zbMATH DE number 1033392 (Why is no real title available?)
• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• An efficient tree decomposition method for permanents and mixed discriminants
• Combinatorics and complexity of partition functions
• Determinantal point processes for machine learning
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Mathematical Foundations of Computer Science 2005
• On the complexity of constrained determinantal point processes
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• The solution of the Kadison-Singer problem

Cited in

(4)

• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• Mathematical Foundations of Computer Science 2005
• A characterization of the mixed discriminant
• Concentration of the mixed discriminant of well-conditioned matrices

This page was built for publication: Stability and complexity of mixed discriminants

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