Monday, December 15, 2008
Institut für Informatik
Rudower Chaussee 25
Humboldt-Kabinett, 1st floor, between house III and IV
Lecture - 14:15
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
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.