IJCAI-2001 Tutorial

August 4th - 10th, 2001
Seattle, Washington, USA

Phase Transitions and Structure in Combinatorial Problems

This tutorial will present an exciting area combining concepts from theoretical physics and artificial intelligence. We will show how the study of phase transition, structure, and related phenomena is changing the way we characterize the computational complexity of combinatorial problems, beyond the notion of worst-case complexity. Furthermore, we will discuss how we can use tools from statistical physics to provide a much more detailed description of a problem's complexity and how we can leverage such insights into the design of search algorithms.

We will describe phase transition behavior observed in a number of different decision problems such as SAT, graph coloring, and number partitioning, as well as optimization problems such as TSP and maximum SAT, and in other complexity classes like P and PSpace.  The second part of the tutorial will cover recent work connecting structural features of problems with phase transition phenomena and computational complexity. Topics covered will include constrainedness, backbone structure, and small world topology.  We will also discuss how to exploit structure and randomness in problems using restart strategies and, more generally, portfolios of algorithms.

The tutorial is aimed at the general AI audience. Familiarity with some basic concepts of combinatorial optimization, probability theory, and computational complexity is desirable but not essential.

Speakers:

Carla P. Gomes is the Director of the Intelligent Information Systems Institute at Cornell University.  Her research has covered several areas in artificial intelligence and computer science, including planning and scheduling, integration of CSP and OR techniques for solving combinatorial problems, and algorithm portfolios.

Tad Hogg is on the research staff of Xerox PARC. His research interests include multiagent systems, smart matter, and the relation between physics and computation, including analogies with physical phase transitions found in combinatorial search

Toby Walsh is an EPSRC Advanced Research Fellow at the Department of Computer Science (York).  He has worked extensively on phase transition behavior in a number of different areas including: satisfiability, constraint satisfaction, traveling salesperson problems, and number partitioning.

Weixiong Zhang is an Associate Professor at Washington University in St. Louis.  His primary research interests include multiagent systems, heuristic search and combinatorial optimization, especially phase transitions and approximation methods that exploit phase transitions.
 

Draft of tutorial slides: part1 and part2.

(More information about this tutorial will be available later.  Meanwhile, if you have any question about the tutorial, please feel free to send a message to one of the speakers.)