[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - October 28th 2019

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

You are cordially invited to our Monday Lecture & Colloquium on October 28th at 14:15 h & 16:00 h at HU Berlin.

Location:

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

Time: Monday, October 28th - 14:15 h

Lecture: Alexandre Vigny (University of Warsaw)

Title: Query enumeration and nowhere dense classes of graphs

Abstract:

Given a query q and a relational structure D the enumeration of q over D consists in computing, one element at a time, the set q(D) of all solutions to q on D. The delay is the maximal time between two consecutive output and the preprocessing time is the time needed to produce the first solution. Idealy, we would like to have constant delay enumeration after linear preprocessing. Since this it is not always possible to achieve, we need to add restriction to the classes of structures and/or queries we consider. In this talk I will talk about some restrictions for which such algorithms exist: graphs with bounded degree, tree-like structures, conjunctive queries... We will more specifically consider nowhere dense classes of graphs: What are they? Why is this notion relevant? How to make algorithms from these graph properties?

Coffee & Tea Break :

Before Humboldt-Kabinett (between House 3&4 / 1st Floor) [British Reading]

Time: Monday, October 28th - 16:00 h

Colloquium: Benjamin Hauskeller (Humboldt-Universität zu Berlin)

Title: Dynamic Query Evaluation with Sublinear Update Time

Abstract:

Dynamic Query Evaluation considers the problem of evaluating a database query on a database using the following framework: In a preprocessing phase the query and an initial database are used to build a data structure which can enumerate the query result on the current database. Upon updates to the database the data structure is adapted to the new database. Research is then interested in the time needed for the preprocessing, the handling of an update, and the maximal delay between tuples during enumeration. In this talk I will present a new class of queries that can be maintained with linear preprocessing time, sublinear update time and constant delay.