[home] - [up]


Lectures and Colloquia during the semester



July 7, 2003

Humboldt-Universität zu Berlin
Rudower Chaussee 25
12489 Berlin
Room 1.115           - map -
Lecture - 14.00 Uhr c.t.

Angelika Steger -Technische Universität München

Probabilistic methods and average case analysis of algorithms

Abstract: NP-completeness of a problem is defined with respect to the worst case analysis of the running time. The drawback of such an analysis is that few or even a single bad instance suffice to get bad bounds. Moreover, worst case examples often require quite intricate constructions and the performance of the given algorithm may be much better on 'typical' instances. Despite the wide acceptance of worst case analysis there is hence a need for additional models which better capture such behavior. A natural approach is to consider the average case for certain distributions of the problem instances. In this talk we present typical examples of average case results and discuss future perspectives. We close this talk with some details on our project "Reconstruction of the Stasi files" where the main difficulty was to replace a trivial quadratic time algorithm by an appropriate linear time average case algorithm.


Colloquium - 16 Uhr s.t.

Manuel Bodirsky -Humboldt-Universität zu Berlin

Homogeneous relational structures, clones from universal algebra, and combinatorial constraint satisfaction

Abstract: Many constraint satisfaction problems can be formulated as a homomorphism problem in the form: For two relational structures S and T of the same type, is there a homomorphism from S to T? For fixed finite T the classification of the tractable problems attracted a lot of interest. We generalize this question to countable homogenous structures T. Homogenous structures, e.g. the Rado graph and the dense linear order, are studied in model theory. We present a characterization of the positive primitive definable relations in T by the clone of polymorphisms of T. The results will be illustrated by many examples with tractable and intractable homomorphism problems and various applications.


[home] - [up] - [top]