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.
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 long-term 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 state-dependant 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".