Christoph Hertrich (Frankfurt): (Old and New) Facets of Neural Network Complexity

How to use discrete mathematics and theoretical computer science to understand neural networks? Guided by this question, I will focus on neural networks with rectified linear unit (ReLU) activations, a standard model and important building block in modern machine learning pipelines. The functions represented by such networks are continuous and piecewise linear. But how does the set of representable functions depend on the architecture? And how difficult is it to train such networks to optimality? In my talk I will answer fundamental questions like these using methods from polyhedral geometry, combinatorial optimization, and complexity theory. This stream of research was started during my doctorate within " Facets of Complexity " and carried much further since then.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Seminar room 053 (ground floor)

Raphael Steiner (ETH Zürich): Shortest paths on combinatorial polytopes: Hardness and approximation

I will present some of my joint work with Jean Cardinal on the complexity of computing and approximating shortest paths in the skeleton of a combinatorially defined polytope. In particular, I will discuss proofs for the inapproximability of finding shortest paths on the skeleton of perfect matching polytopes, and of polymatroids, and discuss various related context and problems in which our work is embedded.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Seminar room 053 (ground floor)

Anand Srivastav (Kiel): Recent Advances in the Maker Breaker Subgraph Game

The triangle game introduced by Chvátal and Erdős (1978) is one of the old and famous combinatorial games. For n , q ∈ N, the ( n , q )-triangle game is played by two players, called Maker and Breaker, on the complete graph K _ n . Alternately Maker claims one edge and thereafter Breaker claims q edges of the graph. Maker wins the game if he can claim all three edges of a triangle. Otherwise Breaker wins. Chvátal and Erdős (1978) proved that for q < sqrt( n /2), Maker has a winning strategy, while for q > 2 sqrt( n ), Breaker wins. So, the threshold bias must be in the interval [sqrt(1/2)sqrt( n ) , 2 sqrt( n )]. Since then, the problem of finding the exact constant (and an associated Breaker strategy) for the threshold bias of the triangle game has been one of the interesting open problems in combinatorial game theory. In fact, the constant is not known for any graph with a cycle and we do not even know if such a constant exists. Balogh and Samotij (2011) slightly improved the Chvátal-Erdős constant for Breaker’s winning strategy from 2 to 1.935 with a randomized approach. Thereafter, no progress was made. In this work, we present a new deterministic strategy for Breaker leading to his win if q > sqrt(8/3) sqrt( n ), for sufficiently large n . This almost matches the Chvátal-Erdős bound of sqrt(1/2)sqrt( n ) for Maker's win (Glazik, Srivastav, Europ. J. Comb. 2022). In contrast to previous (greedy) strategies we introduce a suitable non-linear potential function on the set of nodes. By keeping the potential small, Breaker picks edges that neutralize the most ‘dangerous’ nodes with incident Maker edges blocking Maker triangles. A characteristic property of the dynamics of the game is that the total potential is not monotone decreasing. In fact, the total potential of the game may increase, even for several turns, but finally Breaker’s strategy prevents the total potential of the game from exceeding a critical level, which results in Breaker’s win. We further survey recent results for cycles of length k , and a general potential function theorem (Sowa, Srivastav 2023). This is joint work with Christian Glazik, Christian Schielke and Mathias Sowa, Kiel University.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Great Lecture Hall (Ground Floor)

Dante Luber (TU Berlin): Initial degenerations of Grassmannian via matroid subdivisions of hypersimplices

Nonempty initial degenerations of the Grassmannian are induced by weight functions in its tropicalization. On the other hand, the same weight function induces a regular matroidal subdivision of the hypersimplex. Hence, we study initial degenerations of the (3,8) Grassmannian via matroidal subdivisions of the (3,8) hypersimplex. Our techniques employ tropical, algebraic, and polyhedral geometry, as well as matroid theory, commutative algebra, and computation.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Great Lecture Hall (Ground Floor)

Tibor Szabó (FU Berlin): Topology at the North Pole

In the max-min allocation problem a set P of players are to be allocated disjoint subsets of a set R of indivisible resources, such that the minimum utility among all players is maximized. We study the restricted variant, also known as the Santa Claus problem , where each resource has an intrinsic positive value, and each player covets a subset of the resources. Bezakova and Dani showed that this problem is NP-hard to approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. The principal approach for obtaining approximation algorithms has been via the Configuration LP (CLP) of Bansal and Sviridenko. Accordingly, there has been much interest in bounding the integrality gap of this CLP. The existing algorithms and integrality gap estimations are all based one way or another on the combinatorial augmenting tree argument of Haxell for finding perfect matchings in certain hypergraphs. Here we introduce the use of topological tools for the restricted max-min allocation problem. This approach yields substantial improvements in the integrality gap of the CLP. In particular we improve the previously best known bound of 3.808 to 3.534. The talk represents joint work with Penny Haxell.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Great Lecture Hall (Ground Floor)

Wolfgang Mulzer (FU Berlin): The Multiplicative-Weights-Update Method

The multiplicative weights update method is a design paradigm for algorithms that is used in many different areas of theoretical computer science and machine learning. A famous survey by Arora, Hazan, and Kale provides an excellent overview over the method and its applications. Together with Nabil Mustafa, we are currently working on a monograph that explores the method in more detail. I will give an overview of the method and share some nuggets that we encountered. Based on joint work with Nabil Mustafa.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Great Lecture Hall (Ground Floor)

Günter Rote (Freie Universität Berlin): Grid Peeling and the Affine Curve-Shortening Flow

Grid Peeling is the process of taking the integer grid points inside a convex region and repeatedly removing the convex hull vertices. On the other hand, the Affine Curve-Shortening Flow (ACSF) is defined as a particular deformation of a smooth curve. It has been observed in 2017 by Eppstein, Har-Peled, and Nivasch, that, as the grid is refined, Grid Peeling converges to the Affine Curve-Shortening Flow. As part of the M.Ed. thesis of Moritz Rüber, we have investigated the grid peeling process for special parabolas, and we could observe some striking phenomena. This has lead to the precise value of the constant that relates the two processes. With Morteza Saghafian from IST Austria, we could prove the convergence of grid peeling for the class of parabolas with vertical axis.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Great Lecture Hall (Ground Floor)

Günter Rote (Freie Universität Berlin): The Generalized Combinatorial Lasoń-Alon-Zippel-Schwartz Nullstellensatz Lemma

We survey strengthenings and generalizations of the Schwartz-Zippel Lemma and Alon’s Combinatorial Nullstellensatz. Both lemmas guarantee the existence of (a certain number of) nonzeros of a multivariate polynomial when the variables run independently through sufficiently large ranges.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Great Lecture Hall (Ground Floor)

Andrea Jiménez (Universidad de Varparaíso, Chile): Groundstates of the Ising Model on antiferromagnetic triangulations

We discuss a dual version of a problem about perfect matchings in cubic graphs posed by Lovasz and Plummer. The dual version is formulated as follows "Every triangulation of an orientable surface has exponentially many groundstates'', where groundstates are the states at the lowest energy in the antiferromagnetic Ising Model. According to physicists, this dual formulation holds. In this talk, I show a counterexample to the dual formulation, a method to count groundstates which gives a better bound (for the original problem) on the class of Klee-graphs, the complexity of the related problems and, if time allows, some open problems. This is joint work with Marcos Kiwi and Martin Loebl.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Herman Haverkort (Universität Bonn): Space-filling curves: properties, applications and challenges

A space-filling curve is a continuous, surjective map from [0,1] to a d-dimensional unit volume (for example, a cube or a simplex). Space-filling curves are usually constructed following a recursive tessellation of the unit volume that gives the curve useful structural properties. The most prominent of these properties is that the curve tends to preserve locality: points that are close to each other along the curve are (usually) close to each other in d-dimensional space and (usually) vice versa. This can be exploited to speed up algorithms, in practice and sometimes even in theory, by processing or storing data points in order along the curve. In this lecture I will show how space-filling curves can be described, how they get their useful properties, and I will show examples of their applications. This brings us to the question what would be the optimal space-filling curves for these applications. We will encounter a number of open questions on tessellations in 2D and 3D and on how to measure the quality of a space-filling curve.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Warut Suksompong (National University of Singapore): The Price of Connectivity in Fair Division

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on well-studied fairness notions including envy-freeness and maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. In addition, we determine the optimal relaxation of envy-freeness that can be obtained with each graph for two agents, and characterize the set of trees and complete bipartite graphs that always admit an allocation satisfying envy-freeness up to one good (EF1) for three agents. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems. Joint work with Xiaohui Bei, Ayumi Igarashi, and Xinhang Lu.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Bill Zwicker (Union College, USA): Higher-order Condorcet cycles

In an ordinary Condorcet cycle one can identify, for each candidate, a second candidate preferred, by a majority of voters, to the first.  In a Condorcet cycle of order 2 one can identify, for each pair of candidates, a third candidate preferred, by a majority of voters, to both.  We construct two Condorcet cycles of order 2.  The first, with 11 alternatives and 11 voters, improves the example of 15 alternatives and 15 voters given in [1].  The second, with 7 alternatives and 21 voters, shows that the lower bound on alternatives established in [4] and [3] (and independently in [1]) is sharp. Both our constructions use the method of horizontal rotation , introduced here, which generalizes the more typical form of rotation used to construct standard Condorcet cycles. The second example also makes use of a beautifully symmetric tournament constructed in [3]. William S. Zwicker a (joint work with Davide P. Cervone b ) keywords: Condorcet cycle of order 2, Condorcet winning set, tournament [1] Elkind, E., Lang, J., and Saffidine, A., Condorcet Winning Sets, Soc Choice Welf 44, 493-517 (2015) [2] Erdös, P., On a problem of graph theory, Math Gaz 47, 220-223 (1963) [3] Graham, R.L. and Spencer, J.H., A constructive solution to a tournament problem, Can Math Bul 14, 45-48 (1971) [4] Szekeres, E. and Szekeres,G., On a problem of Schütte and Erdös, Math Gaz 49, 290-293 (1965) a William D Williams Professor of Mathematics Emeritus, Union College, New York; and Murat Sertel Center for Advanced Economic Studies, Istanbul Bilgi University b Mathematics Department, Union College, New York

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Marcel Celaya (ETH, Zürich): Improving the Cook et al. Proximity Bound Given Integral Valued Constraints

Given an optimal solution to a linear program, how far away can a nearest optimal integral solution be? In 1986 Cook, Gerards, Schrijver, and Tardos gave a bound for this distance, known as proximity, which depends only on the dimension and the largest possible magnitude of any subdeterminant of the corresponding constraint matrix. In this talk I will briefly survey this problem, describe some long standing related conjectures, and highlight some recent developments including a recent improvement to the Cook et al. bound when the dimension is at least 2. This is joint work with Joseph Paat, Stefan Kuhlmann, and Robert Weismantel.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Myfanwy Evans (Universität Potsdam): Enumerating triply-periodic tangles

Using periodic surfaces as a scaffold is a convenient route to making periodic entanglements. I will present a systematic way of enumerating new tangled periodic structures, using low-dimensional topology and combinatorics, posing the question of how to best characterise these new patterns. I will also give an insight into applications of these structures.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Michaela Borzechowski (Freie Universität Berlin): Unique Sink Orientations of Grids is in Unique End of Potential Line

The complexity classes Unique End of Potential Line (UEOPL) and its promise version PUEOPL were introduced in 2018 by Fearnly et al. PUEOPL captures search problems where the instances are promised to have a unique solution. UEOPL captures total search versions of these promise problems. The promise problems can be made total by defining violations that are returned as a short certificate of an unfulfilled promise. GridUSO is the problem of finding the sink in a grid with a unique sink orientation. It was introduced by Gärtner et al. in 2008. We describe a promise preserving reduction from GridUSO to UniqueForwardEOPL, a UEOPL-complete problem. Thus, we show that GridUSO is in UEOPL and its promise version is in PUEOPL.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Wolfgang Mulzer (Freie Universität Berlin): Long Alternating Paths Exist

Let P be a set of 2n points in convex position, such that n points are colored red and n points are colored blue. A non-crossing alternating path on P of length l is a sequence p_1, ..., p_l of l points from P so that (i) all points are pairwise distinct; (ii) any two consecutive points p_i, p_{i+1} have different colors; and (iii) any two segments p_i p_{i+1} and p_j p_{j+1} have disjoint relative interiors, for i /= j. We show that there is an absolute constant eps > 0, independent of n and of the coloring, such that P always admits a non-crossing alternating path of length at least (1 + eps)n. The result is obtained through a slightly stronger statement: there always exists a non-crossing bichromatic separated matching on at least (1 + eps)n points of P. This is a properly colored matching whose segments are pairwise disjoint and intersected by a common line. For both versions, this is the first improvement of the easily obtained lower bound of n by an additive term linear in n. The best known published upper bounds are asymptotically of order 4n/3 + o(n). Based on joint work with Pavel Valtr.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Christian Kipp (Technische Universität Berlin): Affine Subspace Concentration Conditions for Polytopes

Given an n-dimensional polytope P and one of its facets F, the cone volume corresponding to F is the volume of conv(0,F). P is said to satisfy the subspace concentration condition w.r.t. a d-dimensional linear subspace L if the total cone volume of the facets with normal vectors in L is at most d/n*vol(P). The subspace concentration condition plays an important role in the context of the (discrete) logarithmic Minkowski problem, i.e., the question: What conditions ensure that a given list of normal vectors and cone volumes can be realized by a polytope? Recently, an affine version of the subspace concentration condition was introduced by Wu for certain lattice polytopes. In this talk, I will focus on the affine case and discuss possible generalizations. This is joint work with Ansgar Freyer and Martin Henk.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Karoly Böröczky (Rényi Institute, Budapest): Facets of the Brascamp-Lieb Inequality and its Reverse form

The Brascamp-Lieb inequality, a generalization of Holder's inequality, is introduced, together with its reverse form generalizing the Prekopa-Leindler due to Barthe. Under certain conditions, the optimal factor in either of inequalities can be obtained using Gaussian test functions. These conditions give rise to the so-called Brascamp Lieb polytope. Algorithmic aspects of approximating the optimal factor  are also discussed.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Andrei Comăneci (Technische Universität Berlin): Tropical Medians by Transportation

The Fermat-Weber problem seeks a point that minimizes the average distance from a given sample. The problem was studied by Lin and Yoshida (2018) using the standard tropical metric with the purpose of analyzing phylogenetic data. In this talk, we argue that using a related asymmetric distance we have better geometric and algorithmic properties. The new formulation is strongly related to tropical convexity and is equivalent to a transportation problem. This gives a geometric perspective to the transportation problem, which was exploited by Tokuyama and Nakano (1995) to obtain efficient algorithms. At the end, we will see an application to computational biology: a new method for computing consensus trees. The talk is based on joint work with Michael Joswig.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Matthias Beck (San Francisco State University): Boundary h*-polynomials of rational polytopes

If P is a lattice polytope (i.e., P is the convex hull of finitely many integer points in R^d), Ehrhart's famous theorem asserts that the integer-point counting function |mP∩Z^d| is a polynomial in the integer variable m. Equivalently, the generating function \sum_{m \ge 0} |mP∩Z^d| t^m is a rational function of the form h*(t)/(1-t)^{d+1}; we call h*(t) the Ehrhart h* - polynomial of P. We know several necessary conditions for h*-polynomials, including results by Hibi, Stanley, and Stapledon, who used an interplay of arithmetic (integer-point structure) and topological (local h-vectors of triangulations) data of a given polytope. We introduce an alternative ansatz to understand Ehrhart theory through the h*-polynomial of the boundary of a polytope, recovering all of the above results and their extensions for rational polytopes in a unifying manner. This is joint work with Esme Bajo (UC Berkeley).

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Imre Bárány (Rényi Institute, Budapest): Cells in the box and a hyperplane

It is well known that a line can intersect at most 2 n −1 cells of the  n × n chessboard. What happens in higher dimensions: how many cells of the  d -dimensional [0, n ]^ d box can a hyperplane intersect? We answer this question asymptotically. We also prove the integer analogue of the following fact. If  K,L are convex bodies in  R ^d and  K ⊂ L , then the surface area  K is smaller than that of  L . This is joint work with Péter Frankl.

Location: Chemistry building Arnimallee 22 14195 Berlin Hörsaal A

János Pach (Rényi Institute, Budapest): Facets of Simplicity

We discuss some notoriously hard combinatorial problems for large classes of graphs and hypergraphs arising in geometric, algebraic, and practical applications. These structures are of bounded complexity: they can be embedded in a bounded-dimensional space, or have small VC-dimension, or a short algebraic description. What are the advantages of low complexity? I will suggest a few possible answers to this question, and illustrate them with classical examples.

Location: Chemistry building Arnimallee 22 14195 Berlin Hörsaal A

Katharina Jochemko (KTH Stockholm): The Eulerian transformation

Many polynomials arising in combinatorics are known or conjectured to have only real roots. One approach to these questions is to study transformations that preserve the real-rootedness property. This talk is centered around the Eulerian transformation which is the linear transformation that sends the i-th standard monomial to the i-th Eulerian polynomial. Eulerian polynomials appear in various guises in enumerative and geometric combinatorics and have many favorable properties, in particular, they are real-rooted and symmetric. We discuss how these properties carry over to the Eulerian transformation. In particular, we disprove a conjecture by Brenti (1989) concerning the preservation of real roots, extend recent results on binomial Eulerian polynomials and provide enumerative and geometric interpretations. This is joint work with Petter Brändén.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Sandro Roch (Technische Universität Berlin): Arrangements of Pseudocircles: On Digons and Triangles

A pseudocircle is a simple closed curve in the plane. An intersecting arrangement of pseudocircles is a finite collection of pseudocircles so that any two intersect in exactly two points where they cross. Grünbaum conjectured in the 1970's that in the case of simple arrangements there are at most 2n - 2 digon cells, i.e. cells which have exactly two crossings on its boundary. I will present a result by Agarwal et al. (2004) which proves this conjecture for the special case of cylindrical arrangements. Based on that we show that the conjecture also holds whenever the arrangement contains three pseudocircles which pairwise form a digon cell. Moreover, I will present a result concerning the number of triangles in digon free arrangements, which disproves another conjecture by Grünbaum. (joint with S.Felsner and M.Scheucher)

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Torsten Ueckerdt (Karlsruher Institut für Technologie, KIT): Stack and Queue Layouts of Planar Graphs

A colored linear layout of a graph is a total ordering of its vertices together with a partition of its edges into color classes. In a stack layout each color class is crossing-free, in a queue layout each color class is nesting-free, while in both cases our goal is to minimize the number of colors. In this talk we discuss on a higher level approaches to find good stack or queue layouts for planar graphs, including some recent breakthroughs and open problems.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Marcel Celaya (ETH, Zürich): Improving the Cook et al. Proximity Bound Given Integral Valued Constraints

Given an optimal solution to a linear program, how far away can a nearest optimal integral solution be? In 1986 Cook, Gerards, Schrijver, and Tardos gave a bound for this distance, known as proximity, which depends only on the dimension and the largest possible magnitude of any subdeterminant of the corresponding constraint matrix. In this talk I will briefly survey this problem, describe some long standing related conjectures, and highlight some recent developments including a recent improvement to the Cook et al. bound when the dimension is at least 2. This is joint work with Joseph Paat, Stefan Kuhlmann, and Robert Weismantel.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Andrew Newman (Carnegie Mellon University, Pittsburgh): Complexes of nearly maximum diameter

The combinatorial diameter of a simplicial complex is the diameter of its dual graph. Using a probabilistic approach we determine the right first-order asymptotics for the maximum possible diameter among all d-complexes on n vertices as well as among all d-pseudomanifolds on n vertices. This is joint work with Tom Bohman.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Jana Novotna (University of Warsaw): Taming Creatures

A graph class is tame if it admits a polynomial bound on the number of minimal separators, and feral if it contains infinitely many graphs with exponential number of minimal separators. The former entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set, and many other problems, when restricted to an input graph from a tame class, by a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015].  In the talk, we show a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame and feral. To obtain the full dichotomy, we confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class C there exists a constant k such that no member of C contains a k-creature or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every graph G from C contains at most p(|V(G)|) minimal separators.  Joint work with Jakub Gajarský, Lars Jafke, Paloma T. Lima, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza.

Location: Humboldt-Universität zu Berlin Institut für Informatik Humboldt-Kabinett (between House 3&4 / 1st Floor [British Reading]) Johann von Neumann-Haus Rudower Chaussee 25 12489 Berlin

Tomáš Masarik (Charles University Prague): Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument

We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw St,t,t as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomassé, SODA 2020] and provide a subexponential-time algorithm with improved running time 2O(n√logn) and a quasipolynomial-time approximation scheme with improved running time 2O(ε−1log5n). The Gyárfás' path argument, a powerful tool that is the main building block for many algorithms in Pt-free graphs, ensures that given an n-vertex Pt-free graph, in polynomial time we can find a set P of at most t−1 vertices, such that every connected component of G−N[P] has at most n/2 vertices. Our main technical contribution is an analog of this result for St,t,t-free graphs: given an n-vertex St,t,t-free graph, in polynomial time we can find a set P of O(tlogn) vertices and an extended strip decomposition (an appropriate analog of the decomposition into connected components) of G−N[P] such that every particle (an appropriate analog of a connected component to recurse on) of the said extended strip decomposition has at most n/2 vertices. In the talk, we first show how Gyárfás' path argument works on Pt-free graphs. Then we will sketch-prove our main result with as few technical details as possible. Joint work with: Konrad Majewski, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokołowski

Location: Humboldt-Universität zu Berlin Institut für Informatik Humboldt-Kabinett (between House 3&4 / 1st Floor [British Reading]) Johann von Neumann-Haus Rudower Chaussee 25 12489 Berlin

Marie Brandenburg (Max Planck Institut Leipzig): Intersection Bodies of Polytopes

Intersection bodies are classical objects from convex geometry, that are constructed from given convex body. In the past, they have mainly been studied from the point of view of convex analysis. In this talk we investigate combinatorial and algebraic structures of intersection bodies of polytopes. We consider an algorithm to compute both the radial function and the algebraic boundary of these intersection bodies, and provide an upper bound for their degree. This is joint work with Katalin Berlow, Chiara Meroni and Isabelle Shankar.

Location: Online via Zoom.

Carlos Amendola (Technische Universität München): Estimating Gaussian mixtures using sparse polynomial moment systems

The method of moments is a statistical technique for density estimation that solves a system of moment equations to estimate the parameters of an unknown distribution. A fundamental question critical to understanding identifiability asks how many moment equations are needed to get finitely many solutions and how many solutions there are.  Since the moments of a mixture of Gaussians are polynomial expressions in the means, variances and mixture weights, one can address this question from the perspective of algebraic geometry. With the help of tools from polyhedral geometry, we answer this fundamental question for several classes of Gaussian mixture models. Furthermore, these results allow us to present an algorithm that performs parameter recovery and density estimation, applicable even in the high dimensional case. Based on joint work with Julia Lindberg and Jose Rodriguez (University of Wisconsin-Madison).

Location: Online via Zoom.

Manuel Radons (Technische Universität Berlin): Nearly flat polytopes in the context of Dürer's problem

Dürer's problem asks whether every 3-polytope P has a net. Is there always a spanning tree T of its edge graph, so that if we cut P along T the resulting surface can be unfolded into the plane without self-overlaps? A common technique in recent works is to fix a spanning tree and then study the deformations of the corresponding unfolding induced by an affine stretching or flattening of P. In the first part of my talk I will highlight landmark results by Ghomi, O'Rourke and Tarasov that emanated from this approach. In the second part I will present my own work on the unfoldability of nested prismatoids, which follows a similar ansatz.

Location: Online via Zoom.

Neil Olver (London School of Economics and Political Science): Continuity, Uniqueness and Long-Term Behaviour of Nash Flows Over Time

We consider a dynamic model of traffic that has received a lot of attention in the past few years. Users control infinitesimal flow particles aiming to travel from a source to destination as quickly as possible. Flow patterns vary over time, and congestion effects are modelled via queues, which form whenever the inflow into a link exceeds its capacity. We answer some rather basic questions about equilibria in this model: in particular uniqueness (in an appropriate sense), and continuity : small perturbations to the instance or to the traffic situation at some moment cannot lead to wildly different equilibrium evolutions. To prove these results, we make a surprising connection to another question: whether, assuming constant inflow into the network at the source, do equilibria always eventually settle into a "steady state" where all queue delays change linearly forever more? Cominetti et al. proved this under an assumption that the inflow rate is not larger than the capacity of the network - eventually, queues remain constant forever. We resolve the more general question positively. (Joint work with Leon Sering and Laura Vargas Koch).

Location: Online via Zoom.

Klaus Heeger (Technische Universität Berlin): Stable Matchings Beyond Stable Marriage

Stable matchings are well-studied from computer science, mathematics, and economics. In the most basic setting, called Stable Marriage, there are two sets of agents. Each agent from one set has preferences over the agents from the other set. A matching assigns the agents into groups of two agents. A matching is called stable if there are no two agents preferring each other to the partners assigned to them. In this talk, we will review important parts of my forthcoming PhD thesis concerning the computational complexity of two extensions of this basic model: First, we assume that an instance of Stable Marriage is given, and the aim is to modify the instance (using as few "modifications" as possible) such that a given edge is part of some stable matching. Second, we assume that agents have preferences over sets of d-1 other agents (for some d>2). In this case, a matching matches agents into groups of size d, and a matching is stable if there are no d agents preferring to be matched together to being unmatched. While since 1991 this problem is known to be NP-complete, we study the case that the preferences of all agents are "similar".

Location: Online via Zoom.

George Mertzios (Durham University, UK): Algorithmic Problems on Temporal Graphs

A temporal graph is a graph whose edge set changes over a sequence of discrete time steps. This can be viewed as a discrete sequence G 1 , G 2 , ... of static graphs, each with a fixed vertex set V . Research in this area is motivated by the fact that many modern systems are highly dynamic and relations (edges) between objects (vertices) vary with time. Although static graphs have been extensively studied for decades from an algorithmic point of view, we are still far from having a concrete set of structural and algorithmic principles for temporal graphs. Many notions and algorithms from the static case can be naturally transferred in a meaningful way to their temporal counterpart, while in other cases new approaches are needed to define the appropriate temporal notions. In particular, some problems become radically different, and often substantially more difficult, when the time dimension is additionally taken into account. In this talk we will discuss some natural but only recently introduced temporal problems and some algorithmic approaches to them. This lecture has been recorded.

Location: Online via Zoom.

Günter Rote (Freie Universität Berlin): The maximum number of minimal dominating sets in a tree

A tree with n vertices has at most 95 n/13 minimal dominating sets. The growth constant λ= 13 √95≈1.4194908 is best possible. It is obtained in a semi-automatic way as a kind of " dominant eigenvalue " of a bilinear operation on sextuples that is derived from the dynamic-programming recursion for computing the number of minimal dominating sets of a tree. The core of the method tries to enclose a set of sextuples in a six-dimensional geometric body with certain properties, which depend on some putative value of λ. This technique is generalizable to other counting problems, and it raises interesting questions about the "growth" of a general bilinear operation. We also derive an output-sensitive algorithm for listing all minimal dominating sets with linear set-up time and linear delay between successive solutions.

Location: Online via Zoom

Ji Hoon Chun (Technische Universität Berlin): The Sausage Catastrophe in dimension 4

The Sausage Catastrophe (Jörg Wills) is the observation that in d = 3 and d = 4, the densest packing of n spheres is a sausage for small n and jumps to a full-dimensional packing for large n without passing through any intermediate dimensions. We denote the smallest value of n for which the densest packing is full-dimensional by k_d. We discuss some upper and lower bounds for k_3 and k_4, including k_3 ≤ 56 by Wills (1985) and k_4 < 375,769 by Gandini and Zucco (1992). We present some initial improvements to the upper bound for k_4 via extending the work of Gandini and Zucco.

Location: Online via Zoom

María A. Hernández Cifre (Universitdad de Murcia): On discrete Brunn-Minkowski type inequalities

The classical Brunn-Minkowski inequality in the n-dimensional Euclidean space asserts that the volume (Lebesgue measure) to the power 1/n is a concave functional when dealing with convex bodies (non-empty compact convex sets). This result has become not only a cornerstone of the Brunn-Minkowski theory, but also a powerful tool in other related fields of mathematics. In this talk we will make a brief walk on this inequality, as well as on its extensions to the Lp-setting, for non-negative values of p. Then, we will move to the discrete world, either considering the integer lattice endowed with the cardinality, or working with the lattice point enumerator, which provides with the number of integer points contained in a given convex body: we will discuss and show certain discrete analogues of the above mentioned Brunn-Minkowski type inequalities in both cases. This is about joint works with Eduardo Lucas and Jesús Yepes Nicolás.

Location: Online via Zoom

Vera Traub (ETH Zürich): Better-Than-2 Approximations for Weighted Tree Augmentation

The Weighted Tree Augmentation Problem (WTAP) is one of the most basic connectivity augmentation problems. It asks how to increase the edge-connectivity of a given graph from 1 to 2 in the cheapest possible way by adding some additional edges from a given set. There are many standard techniques that lead to a 2-approximation for WTAP, but despite much progress on special cases, the factor 2 remained unbeaten for several decades. In this talk we present two algorithms for WTAP that improve on the longstanding approximation ratio of 2. The first algorithm is a relative greedy algorithm, which starts with a simple, though weak, solution and iteratively replaces parts of this starting solution by stronger components. This algorithm achieves an approximation ratio of (1 + ln 2 + ε) < 1.7. Second, we present a local search algorithm that achieves an approximation ratio of 1.5 + ε (for any constant ε > 0). This is joint work with Rico Zenklusen.

Location: online via zoom

Markus Schmid (Humboldt-Universität zu Berlin): Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number

We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that computing the locality number is NP-hard, but fixed-parameter tractable, if parameterised by the locality number or by the alphabet size, which has been formulated as open problems in the literature. Moreover, the locality number can be approximated with ratio O(\sqrt{log(opt)} log(n))$. An important aspect of our work --- that is relevant in its own right and of independent interest --- is that we identify connections between the string parameter of the locality number on the one hand, and the famous graph parameters of cutwidth and pathwidth, on the other hand. These two parameters have been jointly investigated in the literature (with respect to exact, parameterised and approximation algorithms), and are arguably among the most central graph parameters that are based on "linearisations" of graphs. Most importantly, we relate cutwidth with pathwidth via the locality number, which results in an approximation preserving reduction that improves the currently best known approximation algorithm for cutwidth. [This is based on joint work with Katrin Casel, Joel D. Day, Pamela Fleischmann, Tomasz Kociumaka, and Florin Manea, published in Proc. ICALP'19.]

Location: Online via Zoom.

Florin Manea (Universität Göttingen): Combinatorial String Solving

We consider a series of natural problems related to the processing of textual data, rooted in areas as diverse as information extraction, bioinformatics, algorithmic learning theory, or formal verification, and see how they can all be formalized within the same framework. In this framework, we say that a pattern $\alpha$ (that is, a string of string-variables and letters from a fixed alphabet $\Sigma$) matches another pattern $\beta$ if a text $T$, over $\Sigma$, can be obtained both from $\alpha$ and $\beta$ by uniformly replacing the variables of the two patterns by words over $\Sigma$. In the case when $\beta$ contains no variables, i.e., $\beta=T$ is a text, a match occurs if $\beta$ can be obtained from $\alpha$ by uniformly replacing the variables of $\alpha$ by words over $\Sigma$. The respective matching problems, i. e., deciding whether two given patterns match or a pattern and a text match, are computationally hard, but efficient algorithms exist for classes of patterns with restricted structure. In this talk, we overview a series of recent results in this area.

Location: Online via Zoom.

Malte Renken (Technische Universität Berlin): Connectivity Thresholds in Random Temporal Graphs

We consider a simple model of a random temporal graph, obtained by assigning to every edge of an Erdős–Rényi random graph G_n,p a uniformly random presence time in the real interval [0, 1]. We study several connectivity properties of this random temporal graph model and uncover a surprisingly regular sequence of sharp thresholds at which these different levels of connectivity are reached. Finally, we discuss how our results can be transferred to other random temporal graph models. Based on joint work with Arnaud Casteigts, Michael Raskin, and Viktor Zamaraev.

Location: Online via Zoom

Arnaud Casteigts (Université de Bordeaux): Spanners and connectivity problems in temporal graphs

A graph whose edges only appear at certain points in time is called a temporal graph. Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this talk, I will focus on the concept of a temporal spanner, which is a subgraph of the input temporal graph that preserves temporal connectivity using as few edges (or labels) as possible. In stark contrast with standard graphs, it turns out that linear size spanners, and in fact, even sparse spanners (i.e., spanners with o(n ^2 ) edges) do not always exist in temporal graphs. After presenting basic notions and reviewing these astonishing negative results, I will present some good news as well; namely, sparse spanners always exist in *some* natural classes of temporal graphs. These include the cases when the underlying graph is complete (this talk) or when the labels are chosen at random (subsequent talk). If time permit, I will present two open questions, and discuss some recent attempts at solving them.

Location: Online via Zoom

Benjamin Berendsohn (Freie Universität Berlin): Search trees on graphs

Search trees on graphs (STGs) are a generalization of binary search trees (BSTs). Where the key space of a BST is a totally ordered set, the key space of a STG is a graph. STGs are a relatively recent notion, but have been studied previously under different names, including elimination trees, maximal tubings, and vertex rankings. We survey some results. On the computational side, we consider a model of computation for STGs analagous to the BST model, and study which known results for BSTs can be adapted. On the combinatorial side, we study the diameter of certain polytopes called graph associahedra, which can be defined via STGs.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Henry Adams (Institute of Science and Technology Austria): Open questions on clique complexes of graphs

The clique complex of a graph is a simplicial complex with a simplex for each clique. Clique complexes are frequently being computed in applications of topology to data, but we do not understand their algorithmic theory or their mathematical theory. I will introduce clique complexes of graphs, explain why applied topologists care about them, and survey open problems about the topology of clique complexes of unit disk graphs, powers of lattice graphs, and powers of hypercube graphs.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Jonathan Leake (Technische Universität Berlin): Lorentzian polynomials on cones and the Heron-Rota-Welsh conjecture

About 5 years ago, the Heron-Rota-Welsh conjecture (log-concavity of the coefficients of the characteristic polynomial of a matroid) was proven by Adiprasito, Huh, and Katz via the exciting development of a new combinatorial Hodge theory for matroids. In very recent work with Petter Brändén, we have given a new short "polynomial proof" of the Heron-Rota-Welsh conjecture. Our proof uses an extension of the theory of Lorentzian polynomials to convex cones. In this talk, I will briefly discuss the basics of Lorentzian (aka completely log-concave) polynomials, and then I will give an overview of our new proof of the Heron-Rota-Welsh conjecture.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Markus Brill (Technische Universität Berlin): Approval-Based Apportionment

In the apportionment problem, a fixed number of seats must be distributed among parties in proportion to the number of voters supporting each party. We study a generalization of this setting, in which voters cast approval ballots over parties, such that each voter can support multiple parties. This approval-based apportionment setting generalizes traditional apportionment and is a natural restriction of approval-based multiwinner elections, where approval ballots range over individual candidates. Using techniques from both apportionment and multiwinner elections, we identify rules that generalize the D'Hondt apportionment method and that satisfy strong axioms which are generalizations of properties commonly studied in the apportionment literature. In fact, the rules we discuss provide representation guarantees that are currently out of reach in the general setting of multiwinner elections: First, we demonstrate that extended justified representation is compatible with committee monotonicity (also known as house monotonicity). Second, we show that core-stable committees are guaranteed to exist and can be found in polynomial time. Joint work with Paul Gölz, Dominik Peters, Ulrike Schmidt-Kraepelin, and Kai Wilker.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Stefan Kuhlmann (Technische Universität Berlin): Lattice width of lattice-free polyhedra and height of Hilbert bases

A polyhedron defined by an integral valued constraint matrix and an integral valued right-hand side is lattice-free if it does not contain an element of the integer lattice. In this talk, we present a link between the lattice-freeness of polyhedra, the diameter of finite abelian groups and the height of Hilbert bases. As a result, we will be able to prove novel upper bounds on the lattice width of lattice-free pyramids if a conjecture regarding the height of Hilbert bases holds. Further, we improve existing lattice width bounds of lattice-free simplices. All our bounds are independent of the dimension and solely depend on the maximal minors of the constraint matrix. The second part of the talk is devoted to a study of the above-mentioned conjecture. We completely characterize the Hilbert basis of a pointed polyhedral cone when all the maximal minors of the constraint matrix are bounded by two in absolute value. This can be interpreted as an extension of a well-known result which states that the Hilbert basis elements lie on the extreme rays if the constraint matrix is unimodular, i.e., all maximal minors are bounded by one in absolute value. This is joint work with Martin Henk and Robert Weismantel.

Location: online via Zoom

Tim Netzer (Uni Innsbruck): Free Semialgebraic Geometry and Quantum Information Theory

Quantum information theory studies how quantum information can be represented, stored, processed and sent. On the mathematical side this often involves the study of tensor products and decompositions of positive matrices, as well as positive maps. These are also natural objects in free semialgebraic geometry, where positivity of non-commutative objects are studied from a geometric viewpoint. In this talk I will give an introduction to some important concepts in both areas, and demonstrate how results and methods from either field can be successfully employed in the other. This is joint ongoing work between the group of Gemma De las Cuevas and my own research group in Innsbruck.

Location: online via Zoom

Davide Lofano (Technische Universität Berlin): Hadamard Matrix Torsion

After a brief overview about torsion in homology and examples of complexes with small torsion and few vertices we will  focus our attention on a particular series of examples. In particular, we will construct a series HMT(n) of 2-dimensional simplicial complexes with huge torsion, |H_1(HMT(n))|=|det(H(n))|=n^(n/2), where the construction is based on the Hadamard matrices H(n) and they have linearly many vertices in n. Our explicit series improves a previous construction by Speyer, narrowing the gap to the highest possible asymptotic torsion growth achieved by Newman via a randomized construction.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Manfred Scheucher (Technische Universität Berlin): Erdős-Szekeres-type Problems on Planar Point Sets

In 1935, Erdős and Szekeres proved that, for every positive integer k, every sufficiently large point set contains a "k-gon", that is, a subset of k points which is the vertex set of a convex polygon. Their theorem is a classical result in both, combinatorial geometry and Ramsey theory, and motivated a lot of further research including numerous modifications and extensions of the theorem. In this talk we discuss some results and methods that played an essential role in the study of k-gons and the variant of "k-holes".

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Letícia Mattos (Freie Universität Berlin): Singularity of random symmetric matrices

Let M_n be a uniformly-chosen random symmetric n x n matrix with entries in {-1,1}. What is the probability for det(M_n)=0? A wellknown conjecture states that the probability of this event is asymptotically equal to the probability that two of the rows or columns of M_n are equal (up to a factor of +-1) and hence is equal to \Theta(n^2 2^{-n}). We developed an inverse Littlewood-Offord theorem in Z^n_p that applies under very mild conditions and made progress towards this conjecture, showing that the probability is bounded by exp(-c\sqrt{n}). Joint work with Marcelo Campos, Robert Morris and Natasha Morrison.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Florian Frick (Carnegie Mellon University and FU Berlin): Topological methods in graph theory

When we study the structure of a graph, we encounter parameters that are local (such as the clique number) and parameters that are global (such as the chromatic number). Topology provides tools to measure global phenomena. I will explain the hidden topology of the global structure of graphs for problems such as chromatic numbers, covering and matching problems, and partitions into independent sets with various constraints.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Simona Boyadzhiyska (Freie Universität Berlin): Ramsey simplicity of random graphs

We say that a graph G is q-Ramsey for another graph H if any q-coloring of the edges of G yields a monochromatic copy of H. Much of the research related to Ramsey graphs is concerned with determining the smallest possible number of vertices in a q-Ramsey graph for a given H, known as the q-color Ramsey number of H . In the 1970s, Burr, Erdős, and Lovász initiated the study of another graph parameter in the context of Ramsey graphs: the minimum degree.  A straightforward argument shows that, if G is a minimal q-Ramsey graph for H, then we must have δ(G) >= q(δ(H) - 1) + 1, and we say that H is q-Ramsey simple if this bound can be attained. In this talk, we will ask how typical Ramsey simplicity is; more precisely, we will discuss for which pairs p and q the random graph G(n,p) is almost surely q-Ramsey simple. This is joint work with Dennis Clemens, Shagnik Das, and Pranshu Gupta.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Penny Haxell (University of Waterloo): Tashkinov trees - This talk is also introduction to upcoming mini course "Edge colouring of multigraphs" Oct. 26-29

The technique of Tashkinov trees is an important tool that has been used to obtain many significant results on edge colouring of multigraphs. We describe the method and its main motivation, the famous Goldberg-Seymour conjecture from the 1970's. We also outline several results from the last decade that have used the Tashkinov trees technique. This talk is intended as an introduction , overview and survey to accompany the upcoming short course "Edge colouring of multigraphs and the Tashkinov trees method" (Oct 26-29) .

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Raphael Steiner (Technische Universität Berlin): The dichromatic number-a survey

The dichromatic number of a digraph is the smallest number of acyclic subsets of vertices (not spanning a directed cycle) that can be used to cover its vertex-set. This parameter is a natural extension of the chromatic number to directed graphs and has been introduced in 1980 by Erdös and Neumann-Lara. Since 2000, many groups of authors have studied this parameter intensively and in various settings. In this talk, I will give a small survey of this topic, which has concerned me quite a bit in the last 3-epsilon years. I will also mention own results obtained during my PhD at appropriate places.

Location: online

Frédéric Havet (INRIA Sophia-Antipolis): Unavoidability and universality of digraphs

A digraph F is n-unadoidable} (resp. n-universal) if it is contained in every tournament of order n (resp. n-chromatic digraph). Well-known theorems imply that there is an n F such that F is n F -unavoidable (resp. n F -universal) if and only if F is acyclic, (resp. an oriented forest). However, determining the smallest n F for which it occurs is a challenging question. In this talk, we survey the results on unavoidability and universality and detail some recent recults obtained with various co-authors.

Location: online

Ansgar Freyer (Technische Universität Berlin): Shaking a convex body in order to count its lattice points

We prove inequalities on the number of lattice points inside a convex body K in terms of its volume and its successive minima. The successive minima of a convex body have been introduced by Minkowski and since then, they play a major role in the geometry of numbers. A key step in the proof is a technique from convex geometry known as Blascke's shaking procedure by which the problem can be reduced to anti-blocking bodies, i.e., convex bodies that are "located in the corner of the positive orthant". As a corollary of our result, we will obtain an upper bound on the number of lattice points in K in terms of the successive minima, which is equivalent to Minkowski's Second Theorem, giving a partial answer to a conjecture by Betke et al. from 1993. This is a joint work with Eduardo Lucas Marín.

Location: online

Papa Sissokho (Illinois State University): Geometry of the minimal Solutions of a linear diophantine Equation

Let a 1 ,...,a n and b 1 ,...,b m be fixed positive integers, and let S denote the set of all nonnegative integer solutions of the equation x 1 a 1 +...+x n a n =y 1 b 1 +...+y m b m . A solution (x 1 ,...,x n ,y 1 ,...,y m ) in S is called minimal if it cannot be expressed as the sum of two nonzero solutions in S.  For each pair (i,j), with 1 ≤ i ≤ n and 1 ≤ j ≤ m, the solution whose only nonzero coordinates are x i = b j and y j = a i is called a generator .  We show that every minimal solution is a convex combination of the generators and the zero-solution. This proves a conjecture of Henk-Weismantel and, independently, Hosten-Sturmfels.

Location: online

Gorav Jindal (Technische Universität Berlin): Arithmetic Circuit Complexity of Division and Truncation

Given n-variate polynomials f,g,h such that f=g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size poly(s, deg(h)). This solves a special case of division elimination for high-degree circuits (Kaltofen’87 & WACT’16). This result is an exponential improvement over Strassen’s classic result (Strassen’73) when deg(h) is poly(s) and deg(f) is exp(s), since the latter gives an upper bound of poly(s, deg(f)). The second part of this work deals with the complexity of computing the truncations of uni-variate polynomials or power series. We first show that the truncations of rational functions are easy to compute.  We also prove that the truncations of even very simple algebraic functions are hard to compute,unless integer factoring is easy. This is a joint work with Pranjal Dutta, Anurag Pandey and Amit Sinhababu. A pre-print can be found at https://eccc.weizmann.ac.il/report/2021/072/  .

Location: online

Xavier Allamigeon (Inria and Ecole Polytechnique): Formalizing the theory of polyhedra in a proof assistant

In this talk, I will present the project Coq-Polyhedra that aims at formalizing the theory of polyhedra as well as polyhedral computations in the proof assistant Coq. I will explain how the intuitionistic nature of the logic of a proof assistant like Coq requires to define basic properties of polyhedra in a quite different way than is usually done, by relying on a formal proof of the simplex method. I will also focus on the formalization of the faces of polyhedra, and present a mechanism which automatically introduces an appropriate representation of a polyhedron or a face, depending on the context of the proof. I will demonstrate the usability of this approach by establishing some of the most important combinatorial properties of faces, namely that they constitute a family of graded atomistic and coatomistic lattices closed under interval sublattices, as well as Balinski’s theorem on the d-connectedness of the graph of d-polytopes. Finally, I will discuss recent progress on the formal computation of the graph of a polytope directly within the proof assistant, thanks to a certified algorithm that checks a posteriori the output of Avis’ vertex enumeration library lrslib. Joint work with Quentin Canu, Ricardo D. Katz and Pierre-Yves Strub.

Location: online

Patrick Morris (Freie Universität Berlin): Triangle factors in pseudorandom graphs

An (n, d, λ)-graph is an n vertex, d-regular graph with second eigenvalue in absolute value λ. When λ is small compared to d, such graphs have pseudo-random properties. A fundamental question in the study of pseudorandom graphs is to find conditions on the parameters that guarantee the existence of a certain subgraph. A celebrated construction due to Alon gives a triangle-free (n, d, λ)-graph with d = Θ(n^2/3) and λ = Θ(d^2/n). This construction is optimal as having λ = o(d^2/n) guarantees the existence of a triangle in a (n, d, λ)-graph. Krivelevich, Sudakov and Szab ́o (2004) conjectured that if n ∈ 3N and λ = o(d^2/n) then an (n, d, λ)-graph G in fact contains a triangle factor: vertex disjoint triangles covering the whole vertex set.  In this talk, we discuss a solution to the conjecture of Krivelevich, Sudakov and Szab ́o. The result can be seen as a clear distinction between pseudorandom graphs and random graphs, showing that essentially the same pseudorandom condition that ensures a triangle in a graph actually guarantees a triangle factor. In fact, even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition actually guarantees that such a graph G contains every graph on n vertices with maximum degree at most 2.

Location: online

Alexey Pokrovskiy (University College London): Linear size Ramsey numbers of hypergraphs

The size-Ramsey number of a hypergraph H is the minimum number of edges in a hypergraph G whose every 2-edge-colouring contains a monochromatic copy of H. This talk will be about showing that the size-Ramsey number of r-uniform tight path on n vertices is linear in n. Similar results about hypergraph trees and their powers will also be discussed. This is joint work with Letzter and Yepremyan.

Location: online

Alex Postnikov (MIT): Polypositroids

Polypositroids is a class of convex polytopes defined to be those polytopes that are simultaneously generalized permutohedra (or polymatroids) and alcoved polytopes. Whereas positroids are the matroids arising from the totally nonnegative Grassmannian,polypositroids are "positive" polymatroids. We parametrize polypositroids using Coxeter necklaces and balanced graphs, and describe the cone of polypositroids by extremal rays and facet inequalities. We generalize polypositroids to an arbitrary finite Weyl group W, and connect them to cluster algebras and to generalized associahedra. We also discuss membranes, which are certain triangulated surfaces. They extend the notion of plabic graphs from positroids to polypositroids. The talk is based on a joint work with Thomas Lam.

Location: online

Davide Lofano (Technische Universität Berlin): Random Simple-Homotopy Theory

A standard task in topology is to simplify a given finite presentation of a topological space. Bistellar flips allow to search for vertex-minimal triangulations of surfaces or higher-dimensional manifolds, and elementary collapses are often used to reduce a simplicial complex in size and potentially in dimension. Simple-homotopy theory, as introduced by Whitehead in 1939, generalizes both concepts. We take on a random approach to simple-homotopy theory and present a heuristic algorithm to combinatorially deform non-collapsible, but contractible complexes (such as triangulations of the dunce hat, Bing's house or non-collapsible balls that contain short knots) to a point. The procedure also allows to find substructures in complexes, e.g., surfaces in higher-dimensional manifolds or subcomplexes with torsion in lens spaces. (Joint work with Bruno Benedetti, Crystal Lai, and Frank Lutz.)

Location: online

Michael Joswig (Technische Universität Berlin): Tropical bisectors and Voronoi diagrams

We consider norms in real vector spaces where the unit ball is an arbitrary convex polytope, possibly centrally symmetric.  In contrast with the Euclidean norm, the topological shape of bisectors may be complicated.  Our first main result is a formula for the Betti numbers of bisectors of three points in sufficiently general position. Specializing our results to the tropical polyhedral norm then yields structural results and algorithms for tropical Voronoi diagrams.  The tropical distance function plays a key role in current applications of tropical geometry. Joint work with Francisco Criado and Francisco Santos.

Location: online

Aniket Shah (Ohio State University): A q-analogue of Brion's identity

Rogers-Szego polynomials are a family of orthogonal polynomials on the circle. We introduce a generalization of these polynomials which depend on the data of a polytope and prove a vertex sum formula for them when the polytope is smooth. This formula recovers Brion's formula when the parameter q is set to 0.

Location: online

Max Klimm (Technische Universität Berlin): Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games

We settle the complexity of computing an equilibrium in atomic splittable congestion games with player-specific affine cost functions as we show that the computation is PPAD-complete. To prove that the problem is contained in PPAD, we develop a homotopy method that traces an equilibrium for varying flow demands of the players. A key technique for this method is to describe the evolution of the equilibrium locally by a novel block Laplacian matrix where each entry of the Laplacian is a Laplacian again. These insights give rise to a path following formulation eventually putting the problem into PPAD. For the PPAD—hardness, we reduce from computing an approximate equilibrium for bimatrix win-lose games. As a byproduct of our analyse, we obtain that also computing a multi-class Wardrop equilibrium with class-dependent affine cost functions is PPAD-complete as well. As another byproduct, we obtain an algorithm that computes a continuum of equilibria parametrised by the players’ flow demand. For games with player-independent costs, this yields an output-polynomial algorithm. (Joint work with Philipp Warode)

Location: online

Chris Eur (Stanford University): Tautological classes of matroids

We introduce certain torus-equivariant classes on permutohedral varieties which we call "tautological classes of matroids" as a new geometric framework for studying matroids. Using this framework, we unify and extend many recent developments in matroid theory arising from its interaction with algebraic geometry. We achieve this by establishing a Chow-theoretic description and a log-concavity property for a 4-variable transformation of the Tutte polynomial, and by establishing an exceptional Hirzebruch-Riemann-Roch-type formula for permutohedral varieties that translates between K-theory and Chow theory.  This is a joint work with Andrew Berget, Hunter Spink, and Dennis Tseng.

Location: online

Matthieu Rosenfeld (LIRMM): Bounding the number of sets defined by a given MSO formula on trees

Monadic second order logic can be used to express many classical notions of sets of vertices of a graph as for instance: dominating sets, induced matchings, perfect codes, independent sets, or irredundant sets. Bounds on the number of sets of any such family of sets are interesting from a combinatorial point of view and have algorithmic applications. Many such bounds on different families of sets over different classes of graphs are already provided in the literature. In particular, Rote recently showed that the number of minimal dominating sets in trees of order n is at most 95^(n/13) and that this bound is asymptotically sharp up to a multiplicative constant. We build on his work to show that what he did for minimal dominating sets can be done for any family of sets definable by a monadic second-order formula. I will first illustrate the general technique with a really simple concrete example ( Dominating independent sets). Then I will explain how to generalize this into a more general technique. I will end my talk by mentioning a few of the results obtained with this technique.

Location: online

Kolja Knauer (Universitat de Barcelona): On sensitivity in Cayley graphs

Recently, Huang proved the Sensitivity Conjecture, by showing that every set of more than half the vertices of the $d$-dimensional hypercube $Q_d$ induces a subgraph of maximum degree at least $\sqrt{d}$. This is tight by a result of Chung, F\"uredi, Graham, and Seymour. Huang asked whether similar results can be obtained for other highly symmetric graphs. In this lecture we study Huang's question on Cayley graphs of groups. We show that high symmetry alone does not guarantee similar behavior and present three infinite families of Cayley graphs of unbounded degree that contain induced subgraphs of maximum degree $1$ on more than half the vertices. In particular, this refutes a conjecture of Potechin and Tsang, for which first counterexamples were shown recently by Lehner and Verret. The first family consists of dihedrants. The second family are star graphs, these are edge-transitive Cayley graphs of the symmetric group. All members of the third family are $d$-regular containing an induced matching on a $\frac{d}{2d-1}$-fraction of the vertices. This is largest possible and answers a question of Lehner and Verret. On the positive side, we consider Cayley graphs of Coxeter groups, where a lower bound similar to Huang's can be shown. A generalization of the construction of Chung, F\"uredi, Graham, and Seymour shows that this bound is tight for products of Coxeter groups of type $\mathbf{A_n}$, $\mathbf{I_n}(2k+1)$, most exceptional cases and not far from optimal in general. Then, we show that also induced subgraphs on more than half the vertices of Levi graphs of projective planes and of the Ramanujan graphs of Lubotzky, Phillips, and Sarnak have unbounded degree. This yields more classes of Cayley graphs with properties similar to the ones provided by Huang's results. However, in contrast to Coxeter groups these graphs have no large subcubes. Joint with Ignacio Garcia-Marco.

Location: online

Joanna Lada (Merton College Oxford): On colour-bias Hamilton cycles in dense graphs

Location: online

Peter Bürgisser (Technische Universität Berlin): Optimization, Complexity and Invariant Theory

Invariant and representation theory studies symmetries by means of group actions and is a well established source of unifying principles in mathematics and physics. Recent research suggests its relevance for complexity and optimization through quantitative and algorithmic questions. The goal of the lecture is to give an introduction to new algorithmic and analysis techniques that extend convex optimization from the classical Euclidean setting to a general geodesic setting. We also point out surprising connections to a diverse set of problems in different areas of mathematics, statistics, computer science, and physics. The lecture is mainly based on this joint article with Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter and Avi Wigderson: http://arxiv.org/abs/1910.12375

Location: online

Helena Bergold (Fern Universität Hagen): Topological Drawings meet Classical Theorems of Convex Geometry

In this talk we discuss classical theorems from Convex Geometry such as Carathéodory's Theorem in a more general context of topological drawings of complete graphs. In a (simple) topological drawing the edges of the graph are drawn as simple closed curves such that every pair of edges has at most one common point. Triangles of topological drawings can be viewed as convex sets. This gives a link to convex geometry. Our main result is a generalization of Kirchberger's Theorem that is of purely combinatorial nature. For this we introduce a structure called ''generalized signotopes'' which are a combinatorial generalization of topological drawings. We discuss further properties of generalized signotopes. Joint work with Stefan Felsner, Manfred Scheucher, Felix Schröder and Raphael Steiner.

Location: online

Michaela Borzechowski: One-Permutation-Discrete-Contraction is UEOPL-hard

The complexity class Unique End of Potential Line (UEOPL) was introduced in 2018 by Fearnley et al. and contains many interesting search problems. UEOPL captures problems that have either by definition a unique solution, like the Arrival problem, or that are promised to have a unique solution by some property, like the P-Matrix linear complementary problem. Furthermore the problems in UEOPL have the property that the candidate solutions can be interpreted as an exponentially large graph which form a line, i.e. each node has in and out degree at most 1. The solution of each problem is at the end of that line. In 2017, Daskalakis, Tzamos and Zampetakis proved the problem of finding a fixpoint of a contraction map in a continuous space whose existence is guaranteed by the Banach fixed point theorem to be CLS-complete. A discrete version of the contraction problem, called One-Permutation-Discrete-Contraction, is proven to be the first UEOPL-complete problem. This proof is particularly interesting because it is currently the only one of its kind and lays the groundwork for future UEOPL-completeness proofs. This talk will provide an overview of the reduction from the problem Unique-End-of-Potential-Line to One-Permutation-Discrete-Contraction as well as correcting some errors that were done in the original paper.

Location: online

Pavle Blagojević (Freie Universität Berlin): Ten years in one lecture

Ten years ago, in February 2011, I joined the group of Günter M. Ziegler at Freie Universität Berlin. Now, ten years later, I will show you some of the problems in Geometric and Topological Combinatorics that intrigued us, some of which we managed to solve, and sketch some of the crucial ideas, methods, and the tools we had to develop in order to answer them.  We will see how  -- work on the Bárány-Larman conjecture on colored point sets in the plane   gave birth to the Optimal colored Tverberg theorem,  -- the constraint method collected all classical Tverberg type results under one roof    and opened a door towards counter-examples to the topological Tverberg conjecture. Furthermore, we will illustrate how the search for convex partitions of a polygon into pieces of equal area and equal perimeter forced us to  -- study the topology of the classical configuration spaces,  -- construct equivariant cellular models for them,  -- prove a new version of an equivariant Goresky-MacPherson formula for complements of arrangements,  -- revisit a classical vanishing theorem of Frederick Cohen, and explain why these answers are related to the existence of highly regular embeddings and periodic billiard trajectories. Finally, we will talk about  -- equi-partitions of convex bodies by affine hyperplanes, and  -- greedy convex partitions of many measures. These results are joint work with, in chronological order, Günter M. Ziegler, Benjamin Matschke, Florian Frick, Albert Haase, Nevena Palić, Günter Rote, and Johanna K. Steinmeyer.

Location: online

Florian Frick (Carnegie Mellon University): New applications of the Borsuk--Ulam theorem

The classical Borsuk--Ulam theorem states that any continuous map from the d-sphere to d-space identifies two antipodal points. Over the last 90 years numerous applications of this result across mathematics have been found. I will survey some recent progress, such as results about the structure of zeros of trigonometric polynomials, which are related to convexity properties of circle actions on Euclidean space, a proof of a 1971 conjecture that any closed spatial curve inscribes a parallelogram, and finding well-behaved smooth functions to the unit circle in any closed finite codimension subspace of square-intergrable complex functions.

Location: online

Maria Dostert (Royal Institute of Technology): Exact semidefinite programming bounds for packing problems

In the first part of the talk, I present how semidefinite programming methods can provide upper bounds for various geometric packing problems, such as kissing numbers, spherical codes, or packings of spheres into a larger sphere. When these bounds are sharp, they give additional information on optimal configurations, that may lead to prove the uniqueness of such packings. For example, we show that the lattice E 8  is the unique solution for the kissing number problem on the hemisphere in dimension 8. However, semidefinite programming solvers provide approximate solutions, and some additional work is required to turn them into an exact solution, giving a certificate that the bound is sharp. In the second part of the talk, I explain how, via our rounding procedure, we can obtain an exact rational solution of a semidefinite program from an approximate solution in floating point given by the solver. This is a joined work with David de Laat and Philippe Moustrou.

Location: online

CANCELED: Raman Sanyal (Goethe-Universität Frankfurt): From counting lattice points to counting free segments and back

This talk has been canceled on short notice, and will take place at a later time. Ehrhart theory, the art of counting lattice points in convex polytopes, is a cornerstone of the interplay of combinatorics and geometry. Many important combinatorial objects can be modelled as lattice points in polytopes and counting lattice points with respect to dilation yields deep results in combinatorics. Conversely, the combinatorics of polytopes provides a powerful framework for the computation of these counting functions with numerous algebraic/combinatorial consequnces and challenges. A lattice polytope is free if does not contain lattice points other than its vertices. Klain (1999) suggested a generalization of Ehrhart theory by counting free polytopes with $k$ vertices contained in dilates of a given polytope. For $k=1$, this is precisely Ehrhart theory. Determining these counting functions for $k > 1$ is quite challenging. For $k=2$ (free segments), this is related to counting lattice points visible from each other. In the talk I will discuss joint work with Sebastian Manecke on counting free segments in dilates of unimodular simplices. Our main tool is a number-theoretic variant of Ehrhart theory which can be computed using classical results from geometry. The talk will be scenic tour (with impressions from the unusual summer 2020).

Location: online

Alp Müyesser: Rainbow factors and trees

Generalizing a conjecture of Aharoni, Joos and Kim asked the following intriguing question. Let H be a graph on m edges, and let G_i (1<=i<=m) be a sequence of m graphs on the common vertex set [n]. What is the weakest minimum degree restriction we can impose on each G_i to guarantee a rainbow copy of H? Joos and Kim answered this question when H is a Hamilton cycle or a perfect matching. We provide an asymptotic answer when H is an F-factor, or a spanning tree with maximum degree o(n/log n). This is joint work with Richard Montgomery and Yani Pehova.

Location: online

Sampada Kolhatkar: Bivariate chromatic polynomials of mixed graphs

For a graph G=(V,E), the chromatic polynomial X_G counts the number of vertex colourings as a function of number of colours. Stanley’s reciprocity theorem connects the chromatic polynomial with the enumeration of acyclic orientations of G. One way to prove the reciprocity result is via the decomposition of chromatic polynomials as the sum of order polynomials over all acyclic orientations. From the Discrete Geometry perspective, the decomposition is as the sum of Ehrhart polynomials through real braid arrangement. Beck, Bogart, and Pham proved the analogue of this reciprocity theorem for the strong chromatic polynomials for mixed graph. Dohmen–Pönitz–Tittmann provided a new two variable generalization of the chromatic polynomial for undirected graphs. We extend this bivariate chromatic polynomial to mixed graphs, provide a deletion-contraction like formula and study the colouring function geometrically via hyperplane arrangements.

Location: online

Jannik Peters: Efficiency and Stability in Euclidean Network Design

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.

Location: online

Dante Luber: Boundary Complexes for Moduli Spaces of Curves

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.

Location: online

Matthias Himmelmann: Generalized Principal Component Analysis for Algebraic Varieties

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.

Location: online

Filippos Christodoulou: Design and Analysis of Combinatorial Problems in Random Intersection Graphs

Location: online

Kemal Rose:

Location: online

Hussein Houdrouge: Subquadratic High-Dimensional Hierarchical Clustering

Location: online

Stefan Mengel (CNRS): A Biased Introduction to Decomposable Negation Normal Forms

Decomposable Negation Normal Forms (DNNF) are a class of Boolean circuits first introduced by Darwiche in 2001 in the context of artificial intelligence. Since then they have found applications as a flexible framework for encoding Boolean functions in other areas of computer science like theoretical computer science and database theory. In this talk, I will introduce DNNF, discuss some uses and sketch how one can show bounds on their size.

Location: online

Lisa Sauermann (IAS, Princeton): On the extension complexity of low-dimensional polytopes

It is sometimes possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope P is defined to be the minimum number of facets in a (possibly higher-dimensional) polytope from which P can be obtained as a (linear) projection. In this talk, we discuss some results on the extension complexity of random d-dimensional polytopes (obtained as convex hulls of random points on either on the unit sphere or in the unit ball), and on the extension complexity of polygons with all vertices on a common circle. Joint work with Matthew Kwan and Yufei Zhao.

Location: online

Markus Bläser (Universität Saarbrücken): Irreversibility of tensors of minimal border rank and barriers for fast matrix multiplication

Determining the asymptotic algebraic complexity of matrix multiplication is a central problem in algebraic complexity theory. The best upper bounds on the so-called exponent of matrix multiplication if obtained by starting with an "efficient" tensor, taking a high power and degenerating a matrix multiplication out of it. In the recent years, several so-called barrier results have been established. A barrier result shows a lower bound on the best upper bound for the exponent of matrix multiplication that can be obtained by a certain restriction starting with a certain tensor. We prove the following barrier over the complex numbers: Starting with a tensor of minimal border rank satisfying a certain genericity condition, except for the diagonal tensor, it is impossible to prove ω = 2 using arbitrary restrictions. This is astonishing since the tensors of minimal border rank look like the most natural candidates for designing fast matrix multiplication algorithms. We prove this by showing that all of these tensors are irreversible, using a structural characterisation of these tensors. Joint work with Vladimir Lysikov.

Location: online

Sophie Spirkl (University of Waterloo): k-coloring graphs with forbidden induced subgraphs

A k-coloring of a graph G is a function c that assigns an integer between 1 and k to every vertex of G such that c(u) is not equal to c(v) for every edge uv of G. Deciding, given a graph G, whether G has a k-coloring, is NP-hard for all k at least 3. In this talk, we will consider what happens when we restrict the input, that is: For a graph H and integer k, what is the complexity of deciding if a given graph G with no induced subgraph isomorphic to H has a k-coloring? We know the answer for many pairs H and k. Possibly the most interesting open cases are those in which H is a path; I will talk about recent results and open questions related to this.

Location: online

Tillmann Miltzow (Utrecht University): A practical algorithm with performance guarantees for the art-gallery problem

Given a closed simple polygon P, we say two points p,q see each other if the segment pq is fully contained in P. The art gallery problem seeks a minimum size set G⊂P of guards that sees P completely. The only known algorithm to solve the art gallery problem exactly is attributed to Sharir and uses algebraic methods. As the art gallery problem is ∃R-complete, it seems impossible to avoid algebraic methods without additional assumptions. To circumvent this problem, we introduce the notion of vision stability. In order to describe vision stability, consider an enhanced guard that can see "around the corner" by an angle of δ or a diminished guard whose vision is "blocked" by an angle δ by reflex vertices. A polygon P has vision stability δ if the optimal number of enhanced guards to guard P is the same as the optimal number of diminished guards to guard P. We will argue that most relevant polygons are vision-stable. We describe a one-shot algorithm that computes an optimal guard set for vision-stable polygons using polynomial time besides solving one integer program. We implemented an iterative version of the vision-stable algorithm. Its practical performance is slower, but comparable to other state-of-the-art algorithms. Our iterative algorithm is a variation of the one-shot algorithm. It delays some steps and only computes them only when deemed necessary. Given a chord c of a polygon, we denote by n(c) the number of vertices visible from c. The chord-width of a polygon is the maximum n(c) over all possible chords c. The set of vision-stable polygons admits an FPT algorithm when parametrized by the chord-width. Furthermore, the one-shot algorithm runs in FPT time when parameterized by the number of reflex vertices. Joint work by Simon Hengeveld & Tillmann Miltzow.

Location: online

Mikkel Abrahamsen (University of Copenhagen): A framework for ∃R-completeness of two-dimensional packing problems

We show that many natural two-dimensional packing problems are algorithmically equivalent to finding real roots of multivariate polynomials. A two-dimensional packing problem is defined by the type of pieces, containers, and motions that are allowed. The aim is to decide if a given set of pieces can be placed inside a given container. The pieces must be placed so that they are pairwise interior-disjoint, and only motions of the allowed type can be used to move them there. We establish a framework which enables us to show that for many combinations of allowed pieces, containers, and motions, the resulting problem is ∃R-complete. This means that the problem is equivalent (under polynomial time reductions) to deciding whether a given system of polynomial equations and inequalities with integer coefficients has a real solution. We consider packing problems where only translations are allowed as the motions, and problems where arbitrary rigid motions are allowed, i.e., both translations and rotations. When rotations are allowed, we show that the following combinations of allowed pieces and containers are ∃R-complete: - simple polygons, each of which has at most 8 corners, into a square, - convex objects bounded by line segments and hyperbolic curves into a square, - convex polygons into a container bounded by line segments and hyperbolic curves. Restricted to translations, we show that the following combinations are ∃R-complete: - objects bounded by segments and hyperbolic curves into a square, - convex polygons into a container bounded by segments and hyperbolic curves. Joint work by Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth. The paper has been accepted for FOCS.

Location: online

Amitabh Basu (Johns Hopkins University Baltimore): Complexity of cutting plane and branch-and-bound algorithms - cancelled

We present some results on the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In the first part of the talk, we study the relative efficiency of BB and CP, when both are based on the same family of disjunctions. We focus on variables disjunctions and split disjunctions. We extend a result of Dash to the nonlinear setting which shows that for convex 0/1 problems, CP does at least as well as BB, with variable disjunctions. We sharpen this by showing that there are instances of the stable set problem where CP does exponentially better than BB. We further show that if one moves away from 0/1 polytopes, this advantage of CP over BB disappears; there are examples where BB finishes in O(1) time, but CP takes infinitely long to prove optimality, and exponentially long to get to arbitrarily close to the optimal value (for variable disjunctions). Finally, we show that if the dimension is considered a fixed constant, then the situation reverses and BB does at least as well as CP (up to a polynomial blow up). In the second part of the talk, we will discuss the conjecture that the split closure has polynomial complexity in fixed dimension, which has remained open for a while now even in 2 dimensions. We settle it affirmatively in two dimensions, and complement it with a polynomial time pure cutting plane algorithm for 2 dimensional IPs based on split cuts.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

All Monday Lectures of Summer Term 2020 are cancelled.

Mikkel Abrahamsen (University of Copenhagen): Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane - cancelled

We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest "fence" F, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are separated if F contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as GEOMETRIC k-CUT, where k is the number of different colors, as it can be seen as a geometric analogue to the well-studied multicut problem on graphs. We first give an O(n^4 log^3 n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colors and n corners in total. We then show that the problem is NP-hard for the case of three colors. Finally, we give a 4/3*1.2965-approximation algorithm. Joint work with Panos Giannopoulos, Maarten Löffler, and Günter Rote. Presented at ICALP 2019.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Alina Stancu (Concordia University Montréal): Examples and usage of discrete curvature in convex geometry problems - cancelled

Discretization of curvature has found numerous applications particularly in the modeling of moving smooth boundaries separating two different materials and image processing. Nonetheless, there are usually several ways to address discretization of curvature, even in the case of a 1-dimenional object (a curve) depending in essence of the role of the curvature in the physical process or the problem considered. I will present two models of discretization of curvature that I was personally involved with in relation to two geometric problems where the objects considered were also convex.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

CANCELED: Zsolt Ádám Wagner (ETH Zürich): Recent developments in the container method

This colloquium talk is canceled.

José Samper (Max Planck Institut Leipzig): Dual matroid polytopes and the independence complex of a matroid

A shelling order of a simplicial/polytopal complex is an ordering of the top dimensional faces that allows us to understand various properties of the underlying complex (when it exists). Empirically, some shelling orders are better than others in the sense that they are easier to analyze or come equipped with . This is especially notable for complexes that admit many shelling orders, like polytopes and and matroid independence complexes. We propose a strange connection, linking shelling orders of dual matroid polytopes to shelling orders of independence complexes. In particular, we show that several classical theorems about shellability of matroids have geometric interpretations. We use this to address to propose a new strategy for a 1977 conjecture of R. Stanley about face numbers of independence complexes: that the h-vector is a pure O-sequence. The talk is based on joint work with Alex Heaton.

Lionel Pournin (Université Paris 13): Recent results on the diameter of lattice polytopes

Several new results about the largest possible diameter of a lattice polytope contained in the hypercube [0,k]^d, a quantity related to the complexity of the simplex algorithm, will be presented. Upper bounds on this quantity have been known for a couple of decades and have been improved recently. In this lecture, conjecturally sharp lower bounds on this quantity will be presented for all d and k, as well as exact asymptotic estimates when d is fixed and k grows large. These lower bounds are obtained by computing the largest diameter a lattice zonotope contained in the hypercube [0,k]^d can have, answering a question by Günter Rote. This talk is based on joint work with Antoine Deza and Noriyoshi Sukegawa.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)