LSV Seminar

Date

Tuesday, April 07 2009 at 11:00AM

Place

Salle de Conférence (Pavillon des Jardins)

Speaker

Anuj Dawar (Computer Laboratory, University of Cambridge, UK)

It is a long-standing open problem in descriptive complexity theory whether there is a logic that expresses exactly the polynomial-time decidable properties of unordered structures. It has been known since the early 90s that fixed-point logic with counting (FPC) is not sufficient and there have been several proposals for more expressive logics. Taking our inspiration from recent results that show that natural linear-algebraic operations are not definable in FPC, we propose FPR - an extension of fixed-point logic with an operator for matrix rank. We show that this is strictly more expressive than FPC and can express the polynomial-time problems that have been shown to be inexpressible in FPC. We also show that FO+R, the extension of first-order logic with rank operators is surprisingle expressive. It can express some forms of transitive closure and, on ordered structures, captures the complexity classes ModpL.

In this talk, I will give the history and general background to the question (assuming little or no previous knowledge of descriptive complexity and fixed-point logics) and explain the context of the new results. I will also point to several interesting open problems.

(Joint work with Martin Grohe, Bjarki Holm and Bastian Laubner).