Traditionally, there has always been a strong scientific interaction between physicists and mathema ticians in developing physics theories. However, even though numerical computations are now com monplace 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 scientist 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, extremal graph theory, etc.

For instance, when physicists talk about percolation theory, computer scientists would realize that they want to know when a graph has high probability of being connected. Invasion percolation, which occurs, e.g., by injection of a fluid material in a porous medium, and the problem of finding the minimal spanning-tree in a weighted random graph are also identical. Modern simulation methods in computational physics heavily rely on cluster identification, which means simply the detection of connected regions in a graph, or they are based on the construction and modification of hierarchical event trees. Finally, topics from the physics of stochastic processes like random walks play a role in recent algorithmic developments in computer science.

Thus it would be most fruitful to have a forum where physicists inform computer scientists about the problems they are dealing with. In the other direction it is important to keep physicists updated about the most recent algorithmic developments in computer science and in mathematical programming. In particular, in the study of ground states of strongly disordered, amorphous, and glassy materials many algorithms of combinatorial optimization have been applied: Random field systems, interfaces in random media, and diluted antiferromagnets are typical candidates for max-flow/min-cost algorithms; spin glasses are successfully dealt with via matching algorithms and branch-and-cut methods; for flux lines in type-II superconductors and random surface problems minimum-cost-flow algorithms can be applied. The list of interesting physical problems in this context ranges from structural glasses and superconductors over polymers, membranes, and proteins toneural networks. Here in most cases the computation of ground states turns out to be NP-hard or has unknown theoretical complexity. The search for an optimal solution also of these model Hamiltonians is an important task and a real chal lenge for a computer scientist.

The predominant methods used by physicists to study these questions numerically are Monte Carlo simulations and/or simulated annealing. These methods are doomed to fail in the most interesting situations. But, as pointed out above, many useful results in optimization algorithms research never reach the physics community, and interesting computational problems in physics do not come to the attention of algorithm designers. There is a definite need to intensify he interaction between the computer science, mathematical programming, and physics communities.

Thus it should be obvious that an exchange between these three groups has the potential of being fruitful for all sides: The computer scientists will recognize that computational physicists often deal with very similar problems, and try to solve them with a sometimes more pragmatic approach. And the physicists will profit from the most recent algorithmic development that are useful for them but usually reach their community only decades later. This workshop aims at bringing together scientist of all three groups in the pursuit of establishing new interactions. We would ask the participants to give pre sentations that are able to break scientific language barriers, and lay the foundations of new interdis ciplinary work.