• Motivation and scope

In the last years a considerable effort has been devoted by Statistical Physicists to the study of problems issued from Computer Science, Algorithmics, Communication Theory, Combinatorics, ... These works have produced two remarkable effects. First, a new look has been brought to long-standing mathematical problems within these fields. Some remarkably sharp conjectures have been formulated thanks to non-rigorous methods coming from Statistical Physics. Secondly, our community has enlarged its cultural background, and its baggage of ideas, models, tools. Moreover, tackling problems motivated by Computer Science (and similar) has sharpened our understanding of basic physical issues. Despite this positive outcome, we think that it is the right moment for moving beyond the simple relation between disciplines outlined above. This must be done by considering several directions at once:
• The set of problems to be studied must be enlarged and enriched. So far, the main focus has been on some particular problems, whose structure made them particularly suitable for the statistical mechanics analogy. A leit-motiv was, for instance, the underlying graph structure. These limitations must be overcome, and radically different structures explored.
• Many of the statistical physics results must be improved and better understood. While a good global picture exists, in many cases details are still lacking. Moreover incongruencies in our tools are often hidden, stressing the importance of the results, rather than subtle conceptual issues. A fruitful communication with other communities would benefit from a more critic point of view.
• Statistical physics work has focused on the ``intrinsic'' structure of some ensembles of computational tasks. This has been argued to be relevant for the average-case analysis of algorithms. While being relevant in some contexts, such an approach is still not acceptable for many situations where probabilistic models for the input instances do not exist. We have to move forward in order to assess the relevance (or irrelevance) of our results for general complexity theory. The study of randomized approximation algorithms (for instance) could be a bridge in this direction.

• Workshop and invited lecturers

The workshop will gather invited speakers from the Computer Science and the Statistical Physics communities. They will be asked to give long talks for a large audience, focusing on open questions in their domain. The speaker will be asked to be highly informal, and to allow open discussions with the audience. This will be made possible by allowing for flexible time-slots. Invited speakers having confirmed their participation are:
• Prof. D. Aldous (University of California, Berkeley, USA)
• Prof. D. Dean (Cambridge University, UK)
• Prof. S. Franz (Int. Center for Theoret. Physics, Trieste, Italy)
• Prof. M. Goemans (Massachusetts Institute of Technology, USA)
• Prof. L. Kirousis (University of Patras, Greece)
• Prof. M. Mezard (Orsay University, France)
• Prof. M Sudan (Massachusetts Institute of Technology, USA)
• Prof. R. Urbanke (Ecole Polytechnique Federale Lausanne, Switzerland)
• Dr. M. Weigt (Gottingen University, Germany)

• Program

Please click here.

• Location

The workshop will be held at Institut Henri Poincare, in central Paris.

• Satellite conference on ``Optimization algorithms and quantum disordered systems''

A two day follow up devoted to ``Optimization algorithms and quantum disordered systems'', is planned at the same location (IHP in Paris) on June 17. This short and specific conference is made possible by some limited funds from the French Ministry of Research in the framework on a ACI project on the same theme launched in 2000-2001 and ending in 2003-2004. The theme of this conference is closely related to, but more specialized than the SPHINX meeting. See information on this event and invited speakers.

• Registration

please go to the registration web page .