Subject: WORKSHOP: Phase Transitions in Combinatorial Search Problems

From: "Paul Dunne" <[email-masked]>
Date: Sat, 24 Oct 1998 11:05:22 +0100 (BST)

Workshop Announcement and Call for Participation

       Phase Transition Phenomena 
                  in 
     Combinatorial Search Problems
     (January 25th-January 27th 1999)
        University of Liverpool

      (EPSRC/LMS MathfIT Workshop)

As part of the EPSRC/LMS MathfIT initiative, a workshop
on the topic of `Phase Transition Phenomena 
in Combinatorial Search Problems' will be held in Liverpool
between the 25th and 27th January 1999. 

Background

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. 

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, 
Statistical Mechanics, etc - in order 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 for a number of places at this workshop has been provided by
EPSRC (for 12 U.K. EPSRC supported Ph.D students) and by the London
Mathematical Society (for up to 6 non-EPSRC students). Further details
concerning the workshop, including the names of speakers who have accepted
invitations, may be found at:

          http://www.csc.liv.ac.uk/~ptp/