Konstantinos Panagiotou, LMU München

Raum SR005

14:00 - 14:30 Lehrprobe k-Median Problem

14:30 - 15:15 Phase Transitions in Random Constraint Satisfaction Problems

Abstract:

Constraint satisfaction problems (CSPs) are ubiquitous in computer

science and they also serve as important models in several other

disciplines. In an instance of a CSP we are given a set of variables

that can be assigned values in a specified domain, and a set of

constraints that involve subsets of the variables and specify forbidden

assignments to them. The problem is to determine an assignment to the

variables such that no constraint is violated. Prominent examples are

the satisfiability problem and the graph coloring problem.

Many important CSPs are NP-hard; we know of no efficient algorithm that

finds solutions, and we have only very limited knowledge about the

source of the apparent hardness. On the other hand, several CSPs seem to

undergo a dramatic change – a so-called phase transition – regarding

their solvability as the number of constraint surpasses some critical

value. Empirically, the point of this transition is the hotbed of the

most difficult instances for today’s state of the art algorithms. In

this talk I will present a short survey on my recent work regarding the

determination of such phase transitions, and I will report on the

general progress in this active and interdisciplinary area.