BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Descriptive complexity of linear algebra - Holm\, B (University of
  Cambridge)
DTSTART:20120329T130000Z
DTEND:20120329T140000Z
UID:TALK37157@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:An important question that has motivated much work in finite m
 odel theory is that of finding a logical characterisation of polynomial-ti
 me computability. That is to say\, to find a logic in which a class of fin
 ite structures is expressible if\, and only if\, membership in the class i
 s decidable in deterministic polynomial time (PTIME).\n \nMuch of the rese
 arch in this area has focused on the extension of inflationary fixed-point
  logic by counting terms (FPC). This logic has been shown to capture polyn
 omial time on many natural classes of structures\, including all classes o
 f graphs with excluded minors. At the same time\, it is also known that FP
 C is not expressive enough to capture polynomial time on the class of all 
 finite graphs. Noting that the various examples of properties in PTIME tha
 t are not definable in FPC can be reduced to testing the solvability of sy
 stems of linear equations\, Dawar et al. (2009) introduced the extension o
 f fixed-point logic with operators for expressing matrix rank over finite 
 fields (FPR). Fixed-point rank logic strictly extends the expressive power
  of FPC while still being contained in PTIME and it remains an open questi
 on whether there are polynomial-time properties that are not definable in 
 this logic.\n \nIn this talk I give an overview of the main results in the
  logical study of linear algebra and present new developments in this area
 . After reviewing the background to this study\, I define logics with rank
  operators and discuss some of the properties that can be expressed with s
 uch logics. In order to delimit the expressive power of FPR\, I present va
 riations of Ehrenfeucht-Fra&iuml\;ss&eacute\; games that are suitable for 
 proving non-definability in finite-variable rank logics. Using the rank ga
 mes\, I show that if we restrict to rank operators of arity two\, then the
 re are graph properties that can be defined by first-order logic with rank
  over GF(p) that are not expressible by any sentence of fixed-point logic 
 with rank over GF(q)\, for all distinct primes p and q. Finally\, I discus
 s how we can suitably restrict these rank games to get an algebraic game e
 quivalence that can be decided in polynomial time on all classes of finite
  structures. As an application\, this gives a family of polynomial-time ap
 proximations of graph isomorphism that is strictly stronger than the well-
 known Weisfeiler-Lehman method.\n 
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR