University of Leicester


MGS Christmas Seminar 2013

17 December 2013
2pm - 6pm

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 Seminar

Seminar programme

Seminar details

The computational and descriptive complexity of constraint satisfaction problems

Andrei Krokhin (Durham)
17th Dec 2013, 14:15 in ATT LT3

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.

Drift Analysis

Per Kristian Lehre (Nottingham)
17th Dec 2013, 16:00 in ATT LT3

(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.

Simple, efficient, sound-and-complete combinator parsing for all context-free grammars, using an oracle.

Tom Ridge (Leicester)
17th Dec 2013, 17:00 in ATT LT3

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.
© University of Leicester. Last modified: 10th December 2013, 11:41:15
CMS Web Maintainer. Any opinions expressed on this page are those of the author.