Optimization, Complexity and Invariant Theory

Abstract: The Quantum Permanent, the operator(explicitely) and polynomial(just for determinantal polynomials) Capacities were introduced by L.G. in 1999 on the DIMACS Matrix Scaling Workshop. The original motivation for the Quantum Permanent and the Operator Capacity was the Bapat's conjecture, a generalization on the Van Der Waerden conjecture to mixed discriminants. The polynomial capacity first showed up as a natural convex relaxation for the mixed discriminant. These capacities and their generalizations have grown up recently, rather surprisingly to the author, into powerful tools as for algorithms as well for proofs. The most spectacular applications of Operator Capacity is in decision problems, the polynomial capacity is the main engine behind amazingly transparent proofs of hard combinatorial and geometric lower bounds involving hyperbolic and, more generally, strongly log-concave polynomials. I will describe in this talk much less known polynomial time algorithms for several decision problems in the hyperbolic framework. They are possible because of hyperbolic Hall's theorem, a hidden submodularity and other cool things. Time permitting, I will describe the recent deterministic poly-time algorithm for the Quantum permanent of separable bipartite states, where the operator and polynomial capacities meet and need each other. Even more conditionally, I will describe the recent deterministic poly-time algorithm, e.g. a convex relaxation, for the permanent of PSD matrices, where neither Operator Capacity nor Hyperbolicity help, so far...