Monday, December 15, 2008
Humboldt-Universität Berlin
Institut für Informatik
Rudower Chaussee 25
Humboldt-Kabinett, 1st floor, between house III and IV
12489 Berlin
Lecture - 14:15
Abstract:
Descriptive complexity is based on the paradigm that problems hard to solve
algorithmically are hard to describe formally and vice versa. This vague
paradigm is made precise in numerous results stating that logics characterize,
or c a p t u r e, complexity classes.
The central open problem in descriptive complexity theory is the question of
whether there exists a logic capturing PTIME. A good part of my talk will be
an introduction into the background of this question for non-experts (and
non-logicians). Then I will explain a recent result stating that fixed-point
logic with counting captures polynomial time on all classes of graphs with
excluded minors. A consequence of this result is that the Weisfeiler-Lehman
algorithm, a simple and generic combinatorial algorithm, can be used as a
polynomial time isomorphism test for graph classes with excluded minors.
Colloquium - 16:00
Abstract:
Fixed-point logic with counting captures PTIME on many large classes of
graphs, as shown in Martin Grohe's preceding talk. However, it is not
expressive enough to capture PTIME on the class of all structures. For
example, it cannot be used to calculate the rank of a matrix over a
finite field, even though this is a classical polynomial time computation.
In my talk, I will introduce operators that decide the rank of logically
defined matrices. It will be explained that fixed-point logic together
with such rank operators is indeed more expressive than enhancing the
logic with just the ability to count. I will hint at some open problems
in a proof that such a rank logic captures or does not capture PTIME. In
the end, I will show that first-order logic with rank operators over the
two-element field captures the complexity class Parity-L in the presence
of a linear order.