Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, April 28, 2008

Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
Attention: different location: room 4.112.

Lecture - 14:15

Martin Grohe - Humboldt Universität zu Berlin

Bounds and Algorithms for Relational Joins

Relational joins are at the core of relational algebra, which in turn is the core of the standard database query language SQL. As their evaluation is expensive and very often dominated by the output size, it is an important task for database query optimisers to compute estimates on the size of joins and to find good execution plans for sequences of joins. We study these problems from a theoretical perspective, both in the worst-case model, and in an average-case model where the database is chosen according to a known probability distribution. Our key observation is that the size of a sequence of joins is tightly linked to two combinatorial parameters of the underlying database schema, the fractional edge cover number in the worst case scenario, and the maximum density in the average case.

We obtain almost matching upper and lower bounds on the size of the joins in the worst case scenario and a concentration result in the average case. Then we study algorithms for computing joins and, in particular, investigate execution strategies that appear in database systems.

Remarkably, our analysis uses a number of different combinatorial tools, such as entropy arguments, LP duality, expander graphs, and various probabilistic techniques.

(This is joint work with Albert Atserias and Daniel Marx.)

Colloquium - 16:00

Kord Eickmeyer - Humboldt Universität zu Berlin

Approximation of natural W[P]-complete Minimisation Problems is hard

We prove that the weighted monotone circuit satisfiability problem has no fixed-parameter tractable approximation algorithm with constant or polylogarithmic approximation ratio unless FPT = W[P]. The parameterized complexity class FPT consists of all fixed-parameter tractable problems, and the class W[P] may be viewed as an analogue of the class NP in the world of parameterized complexity theory. Our result answers a question of Alekhnovich and Razborov, who proved that the weighted monotone circuit satisfiability problem has no fixed-parameter tractable 2-approximation algorithm unless every problem in the parameterized complexity class W[P] can be solved by a randomized fpt algorithm and asked whether their result can be derandomized.

The decision version of the monotone circuit satisfiability problem is known to be complete for the class W[P]. By reducing them to the monotone circuit satisfiability problem with suitable approximation preserving reductions, we prove similar inapproximability results for all other natural minimisation problems known to be W[P]-complete.

Letzte Aktualisierung: 22.04.2008