Oberseminar Algebraische Komplexitätstheorie

What is the probability that the solution of a random semidefinite program has rank r? This 15 year old question may be answered in terms of certain localizations of the intrinsic volumes of the cone of positive semidefinite matrices. We describe this connection and give closed formulas for these quantities. The resulting formulas involve integrals that resemble Mehta's integral, but for which we could not yet find a closed expression (as is known for Mehta's integral). Our results cover the semidefinite cones over the real, complex, and quaternion numbers.

Given a random quantum state of multiple particles, we have recently provided an algorithm, rooted in symplectic geometry, to compute the joint probability distribution of the eigenvalues of its one-body reduced density matrices (arXiv:1204.0741). This probability distribution is obtained from the corresponding distribution of diagonal entries, which is given by the volume function of a parametric polytope. As I will explain, this is an instance of a more general principle relating invariant measures on compact Lie algebras to their projection onto a Cartan subalgebra. The connection of our work to complexity theory is twofold: First, the probability measures that we compute capture the asymptotic growth of Kronecker and plethysm coefficients, which are of relevance in geometric complexity theory. Second, the reduction procedure described above has a quantized counterpart which gives rise to a polynomial-time algorithm for the branching problem of compact, connected Lie groups.

Just a few months ago, Landsberg and Ottaviani proved the lower bound 2n²-n for the border rank of n × n matrix multiplication, see arXiv.1112.6007. Their methods are based on the fundamental idea that any tensor T can be understood as a linear map f. From f, a new linear map φ is constructed and it is observed that the rank of φ yields a lower bound for the border rank of T. The map φ is then embedded into an exact sequence: By giving explicit, representation-theoretic descriptions of the kernels in this sequence, its rank is computed.

This talk is to present an ongoing project. The average number of real zeros of a random real polynomial is a well-studied problem. For instance, when the coefficients are identically tossed following a normal distribution, the number of zeros is asymptotically logarithmic in the degree.
We here consider random sparse polynomials: polynomials for which a (small) number of nonzero coefficients are tossed. A criterion from Descartes tells us that the number of positive zeros of a sparse polynomial cannot be greater than the number of nonzero coefficients, no matter what the degree is. But no better result is known in the average. Yet, we suspect that the number could be much smaller in the average.
We will discuss the tools we could use to estimate this number of real zeros and what implications it could have in complexity theory.