You are invited to our Monday Lecture & Colloquium on Jan 7th, 2019 at 14:15 h & 16:00 h at FU Berlin. Lecture: Monday, January 7th - 14:15 h =============================================== Péter Pál Pach (Budapest University of Technology and Economics): The polynomial method and the cap set problem =============================================== Abstract: In this talk we will look at a new variant of the polynomial method which was first used to prove that sets avoiding 3-term arithmetic progressions in groups like Z_4^n (Croot, Lev and myself) and Z_3^n (Ellenberg and Gijswijt) are exponentially small (compared to the size of the group). We will discuss lower and upper bounds for the size of the extremal subsets, including some recent bounds found by Elsholtz and myself. We will also mention some further applications of the method, for instance, the solution of the Erdős-Szemerédi sunflower conjecture. Coffee & Tea Break: Room 134 Colloquium: 16:00 h =============================================================== Ardalan Khazraei (Bonn): Cost-distance Steiner trees =============================================================== Abstract: In the well-known Steiner Tree Problem, the objective is to connect a set of terminals at the least total cost. We can further constrain the problem by specifying upper bounds for the distance of each terminal to a chosen root terminal. Further, using the Lagrangian relaxation of this restriction, we can penalize large distances in the objective function rather than applying strict distance constraints. We arrive at a special case of the so-called Cost-Distance Steiner Tree Problem in which we have a single weight function on the edges. In this talk, I will present several results from my master's thesis that concern the Cost-Distance Steiner Tree Problem. The NP-hardness of the Cost-Distance Steiner Tree Problem trivially follows from the fact that the regular Steiner Tree Problem is the special case where we set demand weights (Lagrange multipliers) of the terminals to zero. I therefore proceed to prove that the problem remains NP-hard in three restricted cases that do not contain the regular Steiner Tree Problem as a special case anymore. Then I improve on a previous constant-factor approximation for the single-weighted case by using a hybrid method of an approximate Steiner tree with a shortest path tree replacing sections of the tree where path segments are used by many terminals with demand weights summing to higher than a tunable threshold. I also use a similar approach to extend Arora's dynamic programming method for the two-dimensional geometric Steiner Tree Problem to the case with the penalizing terms in the objective function. Location: Room 005 - Ground Floor Freie Universität Berlin Takustr. 9 14195 Berlin