### Inhalt des Dokuments

# Kolloquium

In unserem Kolloquium algorithmische Mathematik und Komplexitätstheorie tragen Mitarbeiter und Gäste über aktuelle Themen ihrer Forschung vor. Organisiert mit Hilfe von Alperen Ali Ergür.

*In our Kolloquium on algorithmic mathematics and complexity theory, guests and members of the group presents current topics about their research. Organized with the help of Alperen Ali Ergür.*

## Terminplan

Vortragender | Titel | Datum | Zeit |
---|---|---|---|

Kathlén Kohn | Coisotropic Varieties in Algebraic Vision | 21.09.2017 | 14^{15}-15^{45} |

James Mathews | Submanifold jets and envelopes | 28.09.2017 | 14^{15}-15^{45} |

Mario Kummer | Eigenvalues of Symmetric Matrices over Integral Domains | 26.10.2017 | 14^{15}-15^{45} |

Paul Breiding | Random Spectrahedra | 2.11.2017 | 14^{15}-15^{45} |

Christian Ikenmeyer | Width 2 algebraic branching programs and the continuant | 16.11.2017 | 14^{15}-15^{45} |

Guillaume Malod | Lower bounds for restricted arithmetic models | 7.12.2017 | 14^{15}-15^{45} |

Corey Harris | Moved to the 18th of January | 14.12.2017 | 14^{15}-15^{45} |

Boulos El Hilany | Real Hurwitz numbers and simple rational functions | 21.12.2017 | 14^{15}-15^{45} |

Cordian Riener | Homology of Symmetric Semi-Algebraic sets | 11.1.2017 | 14^{15}-15^{45} |

Corey Harris | Computations and applications of Segre classes | 18.1.2017 | 14^{15}-15^{45} |

Pierre Lairez | Quasi-optimal average complexity for finding one root of a polynomial system | 1.2.2017 | 14^{15}-15^{45} |

Rainer Sinn | Quadratic Persistence of Real Projective Varieties | 8.2.2017 | 14^{15}-15^{45} |

Kristin Shaw | Bounding Betti numbers of patchworked real hypersurfaces by Hodge numbers | 15.2.2017 | 14^{15}-15^{45} |

Michael Walter | Quantum marginal problem, tensor scaling, and invariant theory | 22.2.2017 | 15^{15}-16^{45} |

### Submanifold jets and envelopes

**Speaker: **James Mathews

I will introduce a notion of the envelopes of a family of submanifolds or subvarieties, in the generality of arbitrary dimensions and jet-order. The notion has its roots throughout classical geometry (optics, caustics, developable surfaces, confocal quadrics).

The case of plane curves is a surprisingly rich testing ground for the ideas, with applications to projective geometry and web geometry. The Koszul complex makes an unexpected appearance here, suggesting an elegant (though conjectural) computation of envelopes in the completely general case.

This presentation is derived from my PhD thesis at Stony Brook University.

### Coisotropic Varieties in Algebraic Vision

**Speaker: **Kathlén Kohn

This talk will have two parts.

In the first part, we will motivate and define coisotropic varieties as certain subvarieties of Grassmannians.

We will discuss which properties these varieties should have and show first non-trivial examples.

In the second part, we will see how coisotropic varieties appear naturally in Algebraic Vision and how they can lead to new proof techniques in this field. This is based on joint work with Bernd Sturmfels and Matthew Trager.

### Eigenvalues of Symmetric Matrices over Integral Domains

**Speaker:** Mario Kummer (MPI Leipzig)

Given an integral domain A we consider algebraic integers over A that can appear as Eigenvalue of a symmetric matrix over A. We address the question of characterising those algebraic integers as well as the problem of finding the smallest possible size of the corresponding symmetric matrix. The focus will lie on the case where A is the polynomial ring over the real numbers or the ring of integers in an algebraic number field. This has implications on the size of semidefinite programs and on multiplicities of Eigenvalues of graphs.

### Random Spectrahedra

**Speaker: **Paul Breiding (MPI Leipzig)

Spectrahedra are a special class of convex sets, defined to be linear sections of the cone of positive definite matrices. In this talk we will consider random spectrahedra, which are defined for linear sections chosen uniform at random. In this talk we will consider the expected volume of a random spectrahedron and the expected volume of the boundary of a random spectrahedron. If the linear space of intersection is of dimension 4, it is known that the boundary has finitely many singularities (counted in projective space). We will also consider the expected number of those. This will be related to the volume of matrices with double eigenvalues, for which we present an explicit formula. This is joint work with Antonio Lerario.

### Width 2 algebraic branching programs and the continuant

**Speaker:** Christian Ikenmeyer (MPI Saarbrucken)

In 1979 Valiant introduced the complexity class VP_e of families with polynomially bounded formula size. In this talk we study the topological closure VP_e-bar, i.e. the class of polynomials that can be approximated arbitrarily closely by polynomials in VP_e. We describe VP_e-bar with a strikingly simple complete polynomial (in characteristic different from 2): The continuant polynomial, which has rich connections to the theory of continued fractions.

The methods are rooted in the study of algebraic branching programs (ABPs) of small constant width. In 1992 Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction naturally lead to the continuant polynomial.

### Lower bounds for restricted arithmetic models

**Speaker:** Guillaume Malod (Université Paris Diderot)

In arithmetic complexity, the objects computed are polynomials and the models can be formulas or circuits or other variants. In this setting, the main open question, similar to P vs NP, is to determine whether the classes VP and VNP are equal. As in Boolean complexity an answer seems out of reach. One current research endeavor is to get lower bounds and separations for classes defined by restricted models, for instance monotone computations where cancellations are not allowed. In this talk I will start with a detailed presentation of lower bounds in the non-commutative setting, based on Nisan's 1991 paper, and then describe various recent results, which can be seen as implementing a similar strategy. I will end with a brief tour of the most important open questions.

### Real Hurwitz numbers and simple rational functions

**Speaker:** Boulos El Hilany (Universitat Tubingen)

Joint work with Johannes Raul.

We study the problem of counting real simple rational functions f with prescribed ramification data. These correspond to a particular class of oriented real Hurwitz numbers of genus 0. Unlike in the complex situation, the number of such real covers depend on the position of the real branch points.

We introduce a signed count of such functions that is invariant under change of the branch locus, thus providing a lower bound for the actual count. The approach is based on the recent works of Itenberg and Zvonkine which treats the polynomial case.

### Homology of Symmetric Semi-Algebraic sets

**Speaker:** Cordian Riener (Universität Konstanz)

Let $R$ be a real closed field and $S\subset R^k$ be a semi-algebraic set defined by symmetric polynomials whose degree is $d$. We consider the rational cohomology groups of $S$. The action of the symmetric group on $\R^k$ gives these groups the structure of a $S_k$-module. We study the isotypic decomposition of this $S_k$-module and show bounds on the multiplicities of the various irreducible $S_k$ representations that can appear. In particular, we study the irreducible representation, which is naturally isomorphic to the equivariant Homology groups, and given an algorithm with polynomially bounded (in $k$) complexity for computing these equivariant Betti numbers. In the end of the talk, we will sketch how this algorithm can be extended to computing the lower Betti numbers of $S$.

This is joint work with Saugata Basu.

### Computations and applications of Segre classes

**Speaker:** Corey Harris (MPI Leipzig)

A fundamental object in intersection theory is the Segre class s(X,Y) of a subscheme X of a variety Y. In the case that X is regularly embedded, this is just the inverse of the Chern class of the normal bundle. The Segre class is more general though, in that it always exists, even when the normal sheaf is not locally free. Segre classes facilitate the computation of many other important objects, such as Chern-Schwartz-MacPherson classes, Chern-Mather classes, and Milnor classes of hypersurfaces. In this talk, I'll give an explicit formula for the Segre class s(X,Y) when Y is a subvariety of a toric variety and give some applications.

### Quasi-optimal average complexity for finding one root of a polynomial system

**Speaker:** Pierre Lairez (Inria)

How many operations do we need on the average to compute an approximate root of a random Gaussian polynomial system? Beyond Smale's 17th problem that asked whether a polynomial bound is possible, we prove a quasi-optimal bound $\text{(input size)}^{1+o(1)}$. This improves upon the previously known $\text{(input size)}^{\frac32 +o(1)}$ bound.

The new algorithm relies on numerical continuation along rigid continuation paths. The central idea is to consider rigid motions of the equations rather than line segments in the linear space of all polynomial systems. This leads to a better average condition number and allows for bigger steps. We show that on the average, we can compute one approximate root of a random Gaussian polynomial system of $n$ equations of degree at most $D$ in $n+1$ homogeneous variables with $O(n^5 D^2)$ continuation steps. This is a decisive improvement over previous bounds that prove no better than $\sqrt{2}^{\min(n, D)}$ continuation steps on the average.

### Quadratic Persistence of Real Projective Varieties

**Speaker:** Rainer Sinn (FU Berlin)

The goal of the talk is to study the Pythagoras number of polynomials, which is the maximal sum-of-squares length. The sum-of-squares length of a polynomial f is the smallest k such that f is a sum of k squares of polynomials. This turns out to be a subtle problem and we discuss relations to an invariant of real projective varieties that we call quadratic persistence. This invariant can be used to provide lower bounds for the Pythagoras number.

### Bounding Betti numbers of patchworked real hypersurfaces by Hodge numbers

**Speaker:** Kristin Shaw (TU Berlin)

The Smith-Thom inequality bounds the sum of the Betti numbers of a real algebraic variety by the sum of the Betti numbers of its complexification. In this talk I will explain our proof of a conjecture of Itenberg which refines this bound for a particular class of real algebraic projective hypersurfaces in terms of the Hodge numbers of its complexification.

The real hypersurfaces we consider arise from Viro's patchworking construction, which is a powerful combinatorial method for constructing topological types of real algebraic varieties. To prove the bounds conjectured by Itenberg we develop a real analogue of tropical homology and use spectral sequences to compare it to the usual tropical homology of Itenberg, Katzarkov, Mikhalkin, Zharkov. Their homology theory gives the Hodge numbers of a complex projective variety from its tropicalisation.

Lurking in the spectral sequences of the proof are the keys to being able to actually control the topology of the real hypersurface produced from a patchwork.

This is joint work in progress with Arthur Renaudineau.

### Quantum marginal problem, tensor scaling, and invariant theory

**Speaker:** Michael Walter (University of Amsterdam and QuSoft)

Given a vector in a rational representation, can it be distinguished from zero by an invariant polynomial? This problem of deciding semi-stability is a fundamental problem in geometric invariant theory. I will explain why it can be usefully thought of as a generalization of linear programming and describe some situations where it is particularly interesting, including the quantum marginal problem in quantum information theory. I’ll then present a geometric algorithm, called tensor scaling, that solves this problem exactly.