In unserem Kolloquium algorithmische Mathematik und Komplexitätstheorie tragen Mitarbeiter und Gäste über aktuelle Themen ihrer Forschung vor. In der Regel findet das Oberseminar jeden Mittwoch von 10:15 bis etwa 11:45 Uhr im Raum MA 316 statt.

Hier finden Sie die Zusammenfassungen der geplanten Vorträge. 

Speaker: JM Landsberg

The rank and border rank of a tensor are important measures of its complexity. For example, all modern upper bounds for the complexity of matrix multiplication arise from results about the border ranks of tensors.  This talk will focus on a special class of tensors: those satisfying Strassen's commutation relations. This class includes the famous Coppersmith-Winograd tensor and is related to the study of spaces of commuting matrices. There is a dictionary that enables one to prove new results about tensors from known results about spaces of matrices and vice versa. The talk should be accessible to anyone who has seen a tensor at least once in their life.  This is very recent joint work with Mateusz Michalek.

Speaker: Jesko Hüttenhain

We study the coordinate ring of the normalization of a $\operatorname{GL}_n(\mathbb{C})$ orbit closure, i.e. the Zariski closure of $\operatorname{GL}_n(\mathbb{C}).v$ for $v\in V$ where $V$ is some $\operatorname{GL}_n(\mathbb{C})$-module. This coordinate ring has a natural embedding into a larger ring with a nice representation-theoretic description. We give conditions for when these two rings coincide; The goal of the talk is to give a counterexample for the Problem 7.19 in Geometric Complexity Theory: an introduction for geometers by J.M. Landsberg, which is a question about when this equality holds.

Speaker: Paul Breiding

Let $f_1,\ldots,f_n$ be homogeneous polynomials of degree $d$ in the variables $X_1,\ldots,X_n$. We say that $\lambda\in\mathbb C$ is an eigenvalue of the system $f=(f_1,\ldots,f_n)$ if there exists $v \in \mathbb C^n$ such that $f(v)=\lambda v$. If $d=1$, then $f$ is a matrix and $\lambda$ one if its eigenvalues. In this talk we explain why we think that our definition of eigenvalues is a good generalization of the matrix case. In particular, we will compute the distribution of the eigenvalue $\lambda$ if the coefficients of $f$ are chosen at random and then compare the cases $d=1$ and $d>1$.

Speaker: Mario Kummer

A finite morphism between quasi-projective varieties defined over the reals is called real-fibred if the preimage of every real point consists only of real points. After explaining some properties and examples, I will show how real-fibred morphisms pop up in linear, semidefinite and hyperbolic programming (reciprocal linear spaces, hyperbolic polynomials). Then I will present some results in this context from joint works with (separately) Eli Shamovich and Cynthia Vinzant.

Speaker: Holger Eble

Quoting the original abstract: The permanent vs. determinant problem is one of the most important problems in theoretical computer science, and is the main target of geometric complexity theory proposed by Mulmuley and Sohoni. The current best lower bound for the determinantal complexity of the $d \times d$ permanent polynomial is $d^2/2$, due to Mignon and Ressayre in 2004. Inspired by their proof method, we introduce a natural rank concept of polynomials, called the bi-polynomial rank. The bi-polynomial rank is related to width of an arithmetic branching program. The bi-polynomial rank of a homogeneous polynomial $p$ of even degree $2k$ is defined as the minimum $n$ such that $p$ can be written as a summation of $n$ products of polynomials of degree $k$. We prove that the bi-polynomial rank gives a lower bound of the determinantal complexity. As a consequence, the above Mignon and Ressayre bound is improved to $(d-1)^2 + 1$ over the field of reals. We show that the computation of the bi-polynomial rank is formulated as a rank minimization problem. Applying the concave minimization technique, we reduce the problem of lower-bounding determinantal complexity to that of proving the positive semidefiniteness of matrices, and this is a new approach for the permanent vs. determinant problem. We propose a computational approach for giving a lower bound of this rank minimization, via techniques of the concave minimization. This also yields a new strategy to attack the permanent vs. determinant problem.