Phase Transitions, Hard Combinatorial Problems and Message Passing Algorithms (08w5109)

Many of the fundamental questions in natural and engineering sciences have been reduced to hard combinatorial optimization problems. During the last few years, there has been a growing awareness that insights and techniques from the study of phase transitions in physics are relevant to the "average-case" performance of algorithms for random instances of these combinatorial problems. In particular, work on phase transitions in spin glasses inspired the invention of a new class of so-called "message-passing" algorithms for these problems. These algorithms perform astonishingly well in practice, and suggest a host of fascinating mathematical conjectures. In the workshop to take place at the Banff International Research Station on June 8 - 13, 2008 we will examine mathematical, theoretical and applied aspects of these new algorithms.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the US National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnologí­a (CONACYT).