ICTP staff scientist Riccardo Zecchina has teamed with physicists worldwide in an effort to make 'hard' computational problems easier to solve.

Spin Glass Spinoff

"Nature is not embarrassed by difficulties of analysis," said the French physicist Augustin Jean Fresnel.
But physicists are often embarrassed--or at least frustrated--by such difficulties. Problems that nature seems to solve with nonchalant ease yield to the physicist only after painstaking analysis and arduous computation. For example, atoms of iron 'know' how to line up when the material becomes magnetised, but for physicists calculating their configuration is a daunting task.
In the past year new methods of calculation have brought dramatic progress to problems of this general kind. The methods allow a more detailed understanding of certain systems in statistical mechanics. What is more surprising is that the new methods can also be applied to a large family of 'hard' problems in computer science and mathematics.
The roots of the new techniques lie in the study of 'spin glasses,' an area of condensed matter physics that has contributed more than its share of embarrassing difficulties.
A spin glass is something like a ferromagnet but with an added dose of disorder. In the magnet, atomic 'spins' tend to line up in the same direction; in the spin glass, some spins prefer to point the same way, but others favour pointing in opposite directions. Randomness is what makes analysis so difficult.
In the 1980s, Marc Mezard (Université XI Paris-Sud, Orsay, France), Giorgio Parisi (University of Rome La Sapienza, Italy) and former ICTP director Miguel A. Virasoro (University of Rome La Sapienza, Italy) developed an approach to spin glasses called 'the cavity method.'
The basic idea involves removing a selected spin from the system (leaving behind a 'cavity') and then calculating how this small change affects the other spins.
Early work on the cavity method focussed on spin networks with a simple and regular structure; the aim was to calculate statistical properties of collections of many spin-glass systems. Recent innovations have applied the method to less regular networks and to single instances rather than statistical ensembles.
The new techniques were devised about a year ago by ICTP staff scientist Riccardo Zecchina and Mezard, following additional work with Parisi. The inspiration came not only from spin-glass methodology but also from ideas in the theory of error-correcting codes. The calculation of the lowest energy configuration is done by a message-passing protocol, in which messages sent from the edges of the cavity diffuse out to other regions of the network. Zecchina and Mezard call the new variation of the cavity method 'survey propagation.'
The broader significance of this work is that many other problems can be encoded as spin-glass systems. The prototypical example is the problem known as 'satisfiability,' where the task is to assign values of true or false to the variables of a formula in propositional logic. The variables can be represented as spins, with opposite spin directions corresponding to true and false. 'Satisfiability' and several other related problems have practical applications in scheduling, optimisation and other areas.
Additional development of the survey-propagation algorithm was undertaken in the summer of 2002 by a group of about a dozen collaborators from around the world who met in August-September at the School on Statistical Physics, Probability Theory and Computational Complexity and Conference on Typical-Case Complexity, Randomness and Analysis of Search Algorithms. In addition to Mezard, Zecchina and Parisi, the team of researchers included Alfredo Braunstein, Silvio Franz, Michele Leone, Andrea Montanari, Roberto Mulet, Andrea Pagnani, Federico Ricci Tersenghi, and Martin Weigt.
The survey-propagation algorithm has now been implemented in a set of computer programmes. Although the programmes are not yet finely tuned, they routinely handle problems tens or hundreds of times larger than other methods can solve in a reasonable time. That could eventually translate this absolute concept into a tool that computer scientists, information experts and others could find of use.

Brian Hayes
American Scientist

Brian Hayes is a long-time science writer currently on the staff of American Scientist. He visited ICTP for a 10-week study period last fall.

Back to Contents Forward to Commentary

Home