[Facets-of-complexity] Invitation and link to Monday Lecture - December 14th 2020 - online via zoom

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our next Monday Lecture. Next Monday, there will be the hearing of the next PhD candidates.

We will have three talks. Talks will be 30 min. 15 min discussions, 15 min break.
All Monday Lectures and Colloquia of winter term 2020/21 will be given online via zoom.

You may find valid Invitation for zoom throughout all winter term here:
http://www.facetsofcomplexity.de/monday/WS-2020-21/index.html

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Monday Lecture will be on December 14th 2020 at 14:00 h, 15:00, 16:00.

Online via:
Zoom - Invitation

Time: Monday, December 14th - 14:00 h

Lecture: Matthias Himmelmann

Title: Generalized Principal Component Analysis for Algebraic Varieties

Abstract:

The Buchberger-Möller algorithm is a famous symbolic method for finding all polynomials that vanish on a point cloud. It has even been extended to noisy samples. However, the resulting variety does not necessarily represent the topological or geometric structure of the data well. By making use of the Vandermonde matrix, it is possible to find polynomials of a prescribed degree vanishing on the samples. As this matrix is severely ill-conditioned, modifications are necessary. By making use of statistical and algebro-geometric techniques, an algorithm for learning a vanishing ideal that represents the data points‘ geometric properties well is presented. It is investigated that this method -- among various other desirable properties -- is more robust against perturbations in the data than the original algorithm.

Time: Monday, December 14th - 15:00 h

Lecture: Dante Luber

Title: Boundary Complexes for Moduli Spaces of Curves

Abstract:

In 2016, Noah Giansiracua showed that a collection of boundary divisors in the moduli space of genus-0 n-pointed curves has nonempty intersection if and only if all pairwise intersections are nonempty. This result is equivalent to showing that the boundary complex associated to such a moduli space is a flag complex. Kyla Quillin extended Giansiracusa's result to most moduli spaces of genus-g n-pointed curves. We give a complete classification of all (g,n) pairs for which the boundary complex is a flag complex.

Time: Monday, December 14th - 16:00 h

Lecture: Jannik Peters

Title: Efficiency and Stability in Euclidean Network Design

Abstract:

We study the recently proposed Euclidean Generalized Network Creation Game by Bilò et al.[SPAA 2019] and investigate the creation of (beta,gamma)-networks, which are in beta-approximate Nash equilibrium and have a total cost of at most gamma times the optimal cost. In our model we have n agents corresponding to points in Euclidean space create costly edges among themselves to optimize their centrality in the created network. Our main result is a simple O(n^2)-time algorithm that computes a (beta,beta)-network with low beta for any given set of points. Along the way, we significantly improve several results from Bilò et al. and we asymptotically resolve a conjecture about the Price of Anarchy.