"Statistical Physics of Combinatorial Search Problems"

5/7/2004: 10:30am - 12:00pm
11th FL Large Conference Room

Abstract: Recent years have witnessed an explosion in the amount of interdisciplinary research across computer science/AI, physics, biology, sociology, giving rise to new disciplines, such as biologically inspired computing, computational sociology, econophysics, to name a few. Studies at the interface of computer science/physics have been particularly fruitful. Techniques developed in statistical physics have been used to model and study complex dynamics in multi-agent systems, analyze Bayesian inference models, study average case complexity of computational problems, etc. In this tutorial talk I will review some of these approaches. In particular, I will talk about structural similarities of frustrated spin systems (so called "spin glasses") and combinatorial optimization problems (COP), and demonstrate how these similarities can be utilized to study average case computational "hardness" of COP-s, analyze phase transitions between easy/hard regimes, and develop efficient algorithms for solving them.

Last updated: Mon Jun 19 17:44:06 2006