Leicester The MGS Christmas Seminar is an event of the Midlands Graduate School. It would be great if you could let me know if you come and whether you join us for dinner (which is planned to start at 630pm in Kayal close to the railway station). I'll be in the lecture hall ATT LT3 from 2pm on, if you come before I am in office F2 on the first floor of the Computer Science building, or in room F9. On the campus map you find the Attenborough building (ATT LT3 is in the basement) and the Computer Science building in the upper right below Enginieering and above the Student Union. MGS Christmas SeminarSeminar programme
Seminar detailsThe computational and descriptive complexity of constraint satisfaction problems
Andrei Krokhin (Durham) Many computational problems can be cast as constraint satisfaction problems (CSPs).
By restricting types of constraints in different ways, one can obtain an infinite family of CSPs.
The computational and descriptive complexity of the obtained problems depends crucially on
the allowed types of constraints, in a way that can be very well captured by algebraic properties of constraints.
In this talk I will explain the correspondence between the structure of finite algebras and the complexity of CSPs.
Per Kristian Lehre (Nottingham) (partly joint work with Carsten Witt)
Drift analysis is powerful tool for analysis of discrete time stochastic
processes, such as those arising from randomised search heuristics.
Informally, it allows longterm properties of a process, such as hitting
times, to be derived from the drift of the process, ie. the change in
the process in one time step.
This talk presents two new drift theorems. The first theorem provides
tail bounds on the hitting times of stochastic processes with
statedependant drift. The second drift theorem provides hitting times
for stochastic populations subject to evolutionary selection pressure.
Tom Ridge (Leicester) There are lots of problems with existing parsing tools. This talk
discusses an approach to parsing without these problems. It is my
take on "parsing done right".

Author: Alexander Kurz, T: +44 (0) 116 252 5356. 