Phase-Transition phenomena in Combinatorial Search problems have proved a fertile source of research activity over the last decade. While the classical domain in which these have been studied is that of Evolutionary Graph Theory, there has been a considerable growth of interest following the empirical studies of search algorithm costs pioneered by researchers in Artifical Intelligence. Independently of the algorithmic and combinatorial theories, phase-transition effects have long formed an important part of classical models of Physical systems and the rich mathematical study of Percolation Theory.
An informal description of a `phase-transition effect' is as the behaviour whereby `small' changes in certain parameters of a system occasion dramatic shifts in some globally observed behaviour of the system, such shifts being marked by a `sharp threshold' point. A very simple example of this in the change from one material state to a different one as temperature is increased, with the `threshold' being given by melting/boiling point. In combinatorial graph theory, a `similar' phenomenon has been observed with respect to random graphs: if graphs with m(n) edges are selected uniformly at random from the set of n-vertex graphs, then for many properties, Q there is a `threshold function', t(n) such that if m(n)/t(n)<1 a randomly chosen graph `almost certainly' has property Q; and if m(n)/t(n)>1, such a graph `almost certainly' does not have property Q. Much of the recent interest in phase-transition phenomena stems from empirical studies of search heuristics for NP-complete problems: these provide strong evidence that the combinatorial property of a decision problem having a phase-transition with respect to the probability of a random instance having a solution, is mirrored in the typical run-time of methods to find a solution: instances `outside' the threshold region are typically resolved quickly; while the run-time peaks for instances `close to' the threshold point.
The aim of this workshop is to bring together researchers from the various fields in which phase-transition phenomena are an important study - Algorithmics and Computational Complexity Theory, Combinatorial Search, Artificial Intelligence, Percolation Theory - to provide a framework in which these different groups may exchange ideas.
A number of leading figures from these fields have agreed to participate in and present talks at the workshop. It is intended that these presentations should report on the progress and methodologies for studying phase-transitions within the various disciplines and be accessible to Ph.D students researching in Algorithmics, Computational Complexity Theory, Probability Theory, Search methodologies in Artificial Intelligence, and Statistical Mechanics.
Funding to cover expenses of up to 12 EPSRC funded research students has been made available by EPSRC under the Mathfit Initiative.
Funding for up to 6 non-EPSRC students has been provided by the London Mathematical Society. (L.M.S.)
The workshop is being organised at the University of Liverpool by
and will take place at the Moat House Hotel in Liverpool between January 25th and January 27th 1999.
The contributors (and areas of interest) will include: