[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - February 3rd 2020

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

You are cordially invited to our next Monday Lecture & Colloquium on February 3rd - again at regular times - at 14:15 h & 16:00 h at FU Berlin.

Location:

Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin

Time: Monday, February 3rd - 14:15 h

Lecture: Sándor Kisfaludi-Bak (MPI Saarbrücken)

Title: Separators and exact algorithms for geometric intersection graphs

Abstract:

Given n ball-like objects in some metric space, one can define a geometric intersection graph where the vertices correspond to objects, and edges are added for pairs of objects with a non-empty intersection. A separator of a graph is a small or otherwise "nice" vertex set whose removal disconnects the graph into two roughly equal parts. In this talk, we will see some separator theorems for intersection graphs in Euclidean and hyperbolic space. One can use these separators to design simple divide and conquer algorithms for several classical NP-hard problems. It turns out that well-designed separators often lead to subexponential algorithms with optimal running times (up to constant factors in the exponent) under the Exponential Time Hypothesis (ETH).

Coffee & Tea Break:
Room 134

Time: Monday, February 3rd - 16:00 h s.t.

Colloquium: Yanitsa Pehova (University of Warwick)

Title: Characterisation of quasirandom permutations by a pattern sum

Abstract:

We say that a sequence {π_{_i}} of permutations is quasirandom if, for each k>1 and each σ∈S_{_k}, the probability that a uniformly chosen k-set of entries of π_{_i} induces σ tends to 1/k! as i tends to infinity. It is known that a much weaker condition already forces π_{_i} to be quasirandom; namely, if the above property holds for all σ∈S₄. We further weaken this condition by exhibiting sets S⊆S₄, such that if randomly chosen four entries of π_{_i} induce an element of S with probability tending to |S|/24, then {π_{_i}} is quasirandom. Moreover, we are able to completely characterise the sets S with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight. This is joint work with Timothy Chan, Daniel Král', Jon Noel, Maryam Sharifzadeh and Jan Volec.