[Facets-of-complexity] New Year's Monday Lecture & Colloquium - Jan 7, 2019 at FU

[Günter Rote <rote@inf.fu-berlin.de>]

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