direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Kolloquium

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

Terminplan

Geplante Vorträge
Vortragender
Titel
Datum
Zeit
Kathlén Kohn
Coisotropic Varieties in Algebraic Vision
21.09.2017
1415-1545
James Mathews
Submanifold jets and envelopes
28.09.2017
1415-1545
Mario Kummer
Eigenvalues of Symmetric Matrices over Integral Domains
26.10.2017
1415-1545
Paul Breiding
Random Spectrahedra
2.11.2017
1415-1545
Christian Ikenmeyer
Width 2 algebraic branching programs and the continuant
16.11.2017
1415-1545
TBA
TBA
23.11.2017
1415-1545
TBA
TBA
30.11.2017
1415-1545
Guillaume Malod
Lower bounds for restricted arithmetic models
7.12.2017
1415-1545
Corey Harris
Computations and applications of Segre classes
14.12.2017
1415-1545
Boulos El Hilany
TBA
21.12.2017
1415-1545
Cordian Riener
TBA
11.1.2017
1415-1545
TBA
TBA
18.1.2017
1415-1545
TBA
TBA
25.1.2017
1415-1545
Pierre Lairez
TBA
1.2.2017
1415-1545
TBA
TBA
8.2.2017
1415-1545
TBA
TBA
15.2.2017
1415-1545

Abstracts

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.

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.

TBA

Speaker: Boulos El Hilany (Universitat Tubingen)

 

 

TBA

Speaker: Cordian Riener (Universität Konstanz)

 

 

TBA

Speaker: Pierre Lairez (Inria)

 

 

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe