Logik in der Informatik Prof. Dr. Martin Grohe

Descriptive complexity theory relates the computational complexity of algorithmic problems with their descriptional complexity. Boldly stated, problems that are hard to solve on a computer are hard to describe in a formal language and vice versa. More precisely, descriptive complexity theory has established logical characterisations for many natural complexity classes. Such characterisations give an approach to computational complexity that is independent of specific machine models and representations of the input. Logical characterisations of complexity classes are also of interest in database theory. As a matter of fact, the main open question of descriptive complexity, the question of whether there is a logic that capture polynomial time, was first posed in a fundamental paper on database query languages by Chandra and Harel (1982).

While logical characterisations are known for the complexity class NP and most natural complexity classes extending NP, no such characterisations are known for subclasses of NP and, in particular, for the class PTIME. The question for a logical characterisation of PTIME is one of the main open problems in finite model theory and database theory.

In this project, we will study various aspect of the descripte complexity theory of the class PTIME and its subclasses.

References

Here are some recent papers on related to the project. The first is a short survey:

Martin Grohe. The quest for a logic capturing PTIME.

In Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS'08), pp.267-271, 2008.

 

Fixed-Point Definability and Polynomial Time.

In Proceedings of the 23rd International Workshop on Computer Science Logic (CSL'09), 2009. Slides of my CSL-talk.

 

Martin Grohe. Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs,

2009.

 

Anuj Dawar, Martin Grohe, Bjarki Holm, and Bastian Laubner. Logics with Rank Operators.

In Proceedings of the 23rd IEEE Symposium on Logic in Computer Science (LICS'09), 2009.

 

Martin Grohe. Definable tree decompositions.

In Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS'08), pp.406-417, 2008.

Vacancy

Applications are invited for a three year research position in Theoretical Computer Science at the Humboldt-University Berlin. The position is within the research project "Descriptive Complexity of Small Complexity Classes". Candidates are expected to have excellent knowldege in mathematical logic and theoretical computer science. They should preferably have a PhD in Mathematics or Computer Science, but strong candidates without a PhD will also be considered, and they will have the opportunity to work towards a PhD on this position.

Applications materials (including CV, list of publications, and the names of two references) should be sent to the following address until 10. October 2009:

Prof. Dr. Martin Grohe
Humboldt-Universität zu Berlin
Institut für Informatik
Unter den Linden 6
10099 Berlin
Germany

e: grohe@informatik.hu-berlin.de
t: +49 30 2093 3078
f: +49 30 2093 3081

Informal inquiries by email may be addressed to Martin Grohe.