Nearly three years ago, in December 1997, the Dagstuhl Seminar "Algorithmic Techniques in Physics4 took place. Researchers from Computer Science, Mathematics and Physics came together to discuss about algorithmic problems occurring in physics and physical concepts that might be useful in computer science. Bringing together people from three different areas was an experiment that, as all participants agreed in the end, turned out to be a success and, more importantly, should be repeated in the future. This proposal is intended to initiate this repetition.

The original seminar was motivated by the observation that traditionally, there has always been a strong scientific interaction between physicists and mathematicians in developing physical theories. However, even though numerical computations are now commonplace in physics, no comparable interaction between physicists and computer scientists has been developed. Since the last three decades the design and the analysis of algorithms for decision and optimization problems evolved rapidly. Simultaneously, computational methods in theoretical physics became a major research tool causing a fast growing challenge with regards to the underlying algorithmic concepts. The few interactions between physicists and computer scientists were often successful and provided new insights in both fields. For example, in one direction, the algorithmic community has profited from the introduction of general purpose optimization tools like the simulated annealing technique that originated in the physics community. In the opposite direction, algorithms in linear, nonlinear, and discrete optimization have turned out to be useful tools in physics. Surprisingly often physicists and computer scientists are concerned with very similar questions but use a different terminology disguising in this way the significant overlap and preventing fruitful collaboration. Many notions of physicists in particle physics the computer scientists call problems or algorithms in combinatorics and external graph theory.

During the seminar it became clear that the communication that was intended by the organizers was indeed extremely fruitful. The computer scientists realized rather quickly that computational physicists often deal with very similar problems and try to solve them with a sometimes more pragmatic approach. And the physicists profited from the most recent algorithmic development that were useful for them but usually reach their community only decades later. Actually a number of participants (including the organizers) took home various ideas that were later converted into scientific publications. Various algorithms from combinatorial optimization are now standard tools in the computational physics community that studies the properties of ground states of disordered and complex systems. Some problems have been solved, but new ones have emerged. On the other hand, new algorithmic techniques have been developed which might be useful in solving these new problems. A selected list of topics that we intend to treat in this seminar is

• Applications of polynomial optimization algorithms, including their problem specific implementation, to random physical systems. Well established examples here are the max-flow/min-cut algorithm to disordered ferromagnets or the min-cost-flow-algorithm to ensembles of magnetic flux lines.
• Concrete physical realizations of various standard problems in combinatorial optimization.
• New developments in heuristic algorithms for NP-hard physical problems, like the Coulomb- or the spin glass as well as new approaches to stochastic optimization (simulated annealing etc.)
• The computational complexity of various compuationally hard physical problems as they occur in the physics of glassy systems.
• Statistical properties and phase transitions of various standard problems in computer science like the K-sat problem with random inputs etc.
• Scaling behavior of various geometric properties of standard algorithms applied to grid graphs.
• And many more.

To summarize we think that in order that new results in optimization algorithms continue to reach the physics community and that interesting computational problems in physics come to the attention of the algorithmic designer it is a good time to repeat the successful seminar. We want to bring together the computer science, mathematical programming and physics communities in the pursuit of establishing new interactions and refreshing old ones, initiated in the `97 event.