[home] - [up]


Lectures and Colloquia during the semester



October 24, 2005

Konrad-Zuse-Zentrum für Informationstechnik Berlin
Takustraße 7, 14195 Berlin
Room 2005 (lecture hall), ground floor

          - map -


Lecture - 14:15

Harold Kuhn- Princeton University

57 Years of Optimization: Conjectures and Corrections

Abstract: I will present a set of memories about a variety of problems, from the traveling salesman problem to the Hungarian method. I will particularly describe conjectures that have never been settled present some new results on the Hungarian Method that I do not believe have ever been noted (most important an example correcting the geometric interpretation in the literature).


Colloquium - 16:00

Hubert Chen -Humboldt-Universität zu Berlin

The Computational Complexity of Quantified Constraint Satisfaction

Abstract: The constraint satisfaction problem (CSP) is a well-acknowledged framework for modelling and solving computational search problems. A more expressive framework that generalizes the CSP is the quantified constraint satisfaction problem (QCSP). Problems from areas as diverse as graph coloring, game playing, database theory, and non-monotonic reasoning can be naturally formulated in these frameworks.

Both of these problems are, in their general formulation, computationally intractable; the CSP is NP-complete, whereas the QCSP is PSPACE-complete. This intractability has motivated the pursuit of restricted cases of these problems that are tractable. One way to restrict these problems is by prespecifying the types of constraints that may appear. This line of work has its origins in a 1978 paper of Schaefer, who achieved a complexity classification of constraints over a two-element domain, but left open the question of such a classification over domains of larger size. Over the past decade, there has been dramatic progress on this question, largely due to a link between universal algebra and CSP complexity that has been identified.

This talk demonstrates how, with this link, algebraic techniques can be used to study QCSP complexity. We develop a new methodology for proving QCSP tractability results called collapsibility, which allows us to

We then discuss the question of how this methodology might be used to achieve a full classification of QCSP complexity.


[home] - [up] - [top]