In unserem Kolloquium algorithmische Mathematik und Komplexitätstheorie tragen Mitarbeiter und Gäste über aktuelle Themen ihrer Forschung vor.

Das Oberseminar findet dienstags von 10:15 bis etwa 11:45 Uhr im Raum MA 316 statt.

Speaker: Anders Hansen (Cambridge)

This talk addresses some of the fundamental barriers in the theory of computations. Many computational problems can be solved as follows: a sequence of approximations is created by an algorithm, and the solution to the problem is the limit of this sequence (think about computing eigenvalues of a matrix for example). However, as we demonstrate, for several basic problems in computations such as computing spectra of operators, solutions to inverse problems, roots of polynomials using rational maps, solutions to convex optimization problems, imaging problems etc. such a procedure based on one limit is impossible. Yet, one can compute solutions to these problems, but only by using several limits. This may come as a surprise, however, this touches onto the boundaries of computational mathematics. To analyze this phenomenon we use the Solvability Complexity Index (SCI). The SCI is the smallest number of limits needed in order to compute a desired quantity. The SCI phenomenon is independent of the axiomatic setup and hence any theory aiming at establishing the foundations of computational mathematics will have to include the so called SCI Hierarchy. We will specifically discuss the vast amount of classification problems in this non-collapsing complexity/computability hierarchy that occur in inverse problems, compressed sensing problems, l1 and TV optimization problems, spectral problems, PDEs and computational mathematics in general.

Speaker: Antonio Lerario (SISSA, Trieste)

What is the expected "topology" of the intersection of random quadric hypersurfaces in $\mathbb{RP}^n$? For $n=2$, the answer follows from a (1993) result of M. Shub and S. Smale: two random conics intersect, on average, in two points (for a natural definition of "random conic"). In the general case $n>2$, the intersection can have higher order nonzero Betti numbers. In this talk I will combine techniques from Algebraic Topology (spectral sequences) with ideas from Random Matrix Theory to study the asymptotic distribution of these Betti numbers. (This is joint work with E. Lundberg)

Speaker: Peter Bürgisser

The permanent versus determinant conjecture is a major problem in complexity theory that is equivalent to the separation of the complexity classes $\mathrm{VP}_{\rm ws}$ and $\mathrm{VNP}$. Mulmuley and Sohoni (SIAM J Comput, 2008) suggested to study a strengthened version of this conjecture over the complex numbers that amounts to separating the orbit closures of the determinant and padded permanent polynomials. In that paper it was also proposed to separate these orbit closures by exhibiting occurrence obstructions, which are irreducible representations of $\operatorname{GL}_{n^2}(\mathbb C)$, which occur in one coordinate ring of the orbit closure, but not in the other. We prove that this approach is impossible.

Speaker: Kathlen Kohn

Gel'fand, Kapranov and Zelevinsky show in their famous book the following: The coisotropic hypersurfaces in Grassmannians are exactly the higher associated hypersurfaces to projective varieties. This talk gives a more direct proof for this and other characterizations of coisotropy. The degrees of coisotropic hypersurfaces will be investigated, as well as how to compute coisotropic hypersurfaces and how to recover their projective varieties. Additionally, the coisotropic hypersurfaces of a projective variety and its dual will be related. 

Speaker: Paul Breiding

The spectral theory of tensors aims at generalizing the theory of eigenvalues of matrices to higher dimensional arrays, called tensors.

It is well known that a generic comples $n\times n$ matrix has exactly $n$ eigenvalues. Similarly, the number of eigenvalues of a complex tensor is generically constant. This was proven by Cartwright and Sturmfels. As in the matrix case, this genericity is not true over the reals. Endowing the space of real tensors with a probability distribution one can, however, compute the expected number of real eigenvalues of a real tensor. 

In this talk I will present the history of this rather young field of research, pioneered by Lim and Qi in the early 2000s. In particular I will first discuss what is the "right" definition of eigenvalues of a tensor and then talk about the expected number of real eigenvalues when the entries of the tensor are centered real gaussian random variables.

Speaker: Felipe Cucker

The best upper bound for the time necessary for computing all the Betti numbers of a real projective set is doubly exponential in the dimension of the ambient space. We give a new algorithm that out of a set of negligible size does this task in single exponential time. 

In this talk, we will discuss the branching problem for compact connected Lie groups as well as its asymptotics, which can be described by moment polytopes from symplectic geometry. I will first give an introduction to the general theory and then report on some new algorithms and complexity theoretic results, with a particular focus on the Kronecker coefficients.