Phase Transitions in Search

» T. Hogg, B. A. Huberman and C. Williams, Phase Transitions and the Search Problem, 1996
A tutorial on phase transitions in search

» C. P. Williams and T. Hogg, Exploiting the Deep Structure of Constraint Problems, 1994
A theory describing why the phase transitions occur and the approximate location of the transition point, with comparison to empirical observations and extensions to a variety of search problems

» T. Hogg and C. P. Williams, The Hardest Constraint Problems: A Double Phase Transition, 1994
Hard problems are concentrated around the phase transition, but there are also rare, extremely hard cases far from the transition region, indicating more complex behaviors

» T. Hogg, Applications of Statistical Mechanics to Combinatorial Search Problems, 1995
A review of the phase transition examining problem classes representing some more realistic types of constraint situations

» T. Hogg, Which Search Problems Are Random?, 1998
Analysis of the structure of hard problems using approximate entropy

The existence of regions of hard and easy problems raises the question of whether some search methods are particularly well suited for the hard instances.

» Cooperative problem solving
is a powerful method for approaching difficult problems.

» T. Hogg and C. P. Williams, Expected Gains from Parallelizing Constraint Solving for Hard Problems, AAAI94
Simple, independent parallel search is effective for some of the hard problem instances

» B. A. Huberman, R. M. Lukose and T. Hogg, An Economics Approach to Hard Computational Problems, 1997
Computational portfolios, analogous to financial portfolios in economics, help solve hard problems

The phase transition relates problem structure with likely search cost. From a practical point of view, can knowledge of the phase transition be exploited directly as a search heuristic?

» S. H. Clearwater and T. Hogg, Problem Structure Heuristics and Scaling Behavior for Genetic Algorithms, 1995
One example where the phase transition can be used to improve search is in genetic algorithms solving constraint satisfaction problems

» T. Hogg, Exploiting Problem Structure as a Search Heuristic, 1995
Another example, with more modest improvement, is for backtrack search

Other types of phase transitions can also appear in more general searches.

» B. A. Huberman and T. Hogg, Phase Transitions in Artificial Intelligence Systems, 1987
Phase transitions in heuristic backtrack search

» C. P. Williams and T. Hogg, The Typicality of Phase Transitions in Search, 1993
An extended analysis of phase transitions in heuristic backtrack search

» T. Hogg and J. O. Kephart, Phase Transitions in High-Dimensional Pattern Classification, 1990
Phase transitions can also appear in the behavior of database retrieval

» J. Shrager, T. Hogg and B. A. Huberman, Observation of Phase Transitions in Spreading Activation Networks, 1987
and in spreading activation networks

» T. Hogg and B. A. Huberman, Artificial Intelligence and Large Scale Computation: A Physics Perspective, 1987
A more general discussion of analogies from physics applying to search and other computational problems in artificial intelligence

» J. Shrager, T. Hogg and B. A. Huberman, A Graph-Dynamic Model of the Power Law of Practice and the Problem-Solving Fan-Effect, 1988
Statistical models also describe learning behavior (for people as well as sophisticated search methods) such as the power law of practice

These papers also contain numerous references to other studies of the phase transition behavior.

Phase transitions also appear in search algorithms for quantum computers using problem structure.

» talk on phase transitions in NP-complete problems from IJCAI91