##### Personal tools

# News from ICTP 103 - What's New

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

**Spin Glass Spinoff**

"**N**ature 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.
*