cms

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.

---

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

---

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

---