We prove that it is #P-hard to compute the mixed discriminant of rank 2 positive semidefinite matrices. We present poly-time algorithms to approximate the "beast". We also prove NP-hardness of two problems related to mixed discriminants of rank 2 positive semidefinite matrices. One of them, the so called Full Rank Avoidance problem, had been conjectured to be NP-Complete in [23] and in [25]. We also present a deterministic poly-time algorithm computing the mixed discriminant D(A_1,..,A_N) provided that the linear (matrix) subspace generated by {A_1,..,A_N} is small and discuss randomized algorithms approximating mixed discriminants within absolute error.
展开▼
