STIPCO European network

A network on
'Statistical physics of Information Processing and Combinatorial Optimisation'
Network of the Research Training Network programme of the European Commision.
Scientific Coordinator: Marc Mézard
E-mail: mezard@ipno.in2p3.fr
The STIPCO network has been approved by the EC as a Research Training Networks, contract number HPRN-CT-2002-00319
The network focuses onto the training of young researchers in the use of statistical physics to study complex systems in realms that are at the borderline of physics: Combinatorial Optimization, Error Correcting Codes, Biological systems, Interacting agents in financial markets and socio-economic systems. You can find the whole text of the proposal in:
The network has started its activity since october 1st, 2002
Here is the list of the various groups building the network, and the name of the scientist responsible for each of them.
ORSAY (France): Marc Mezard,mezard@ipno.in2p3.fr
ASTON (UK): David Saad, d.saad@aston.ac.uk
BARCELONA (Spain): Felix Ritort, ritort@ffn.ub.es
FRIBURG (Switzerland): Zhang Yi Cheng,Yi-Cheng.Zhang@unifr.ch
KOELN (Germany): Michael Laessig, lassig@thp.Uni-Koeln.DE
OXFORD (UK): David Sherrington, m.barnes1@physics.oxford.ac.uk
PARIS ENS (France): Remi Monasson, Remi.Monasson@lpt.ens.fr
ROMA I (Italy): Enzo Marinari, Enzo.Marinari@roma1.infn.it
TRIESTE (Italy): Matteo Marsili, marsili@sissa.it
WEIZMANN (Israel): Eytan Domany, fedomany@wicc.weizmann.ac.il
POSTDOCS

POSTDOC POSITIONS:
Over the period fall 2002 to fall 2006, the STIPCO network has hired 13 post-docs and 2 pre-docs in the various laboratories participating to the network.
TRAINING

TRAINING SCHOOL 2003:
A first training school has taken place in Les Houches from March 3 to March 7, 2003. This school is a program organised jointly with the european network "DYGLAGEMEM". It consisted of 18 hours of lectures, mainly around the following topics: Structural glasses: mode coupling theory, numerical simulations, kinetic constraints. Spin glasses: experiments, theory, simulations. Optimization: K-satisfiability, analysis of algorithms. Error correcting codes. Econophysics. Clustering analysis and DNA chip experiments. On top of these lectures, a series of seminars has been organised.

TRAINING SCHOOL and CONFERENCE 2004:
A training school, together with a conference on "Fundamental Aspects of Complexity", has taken place in Trieste from September 6 to september 10, 2004. This was a program organised jointly with the Abdus Salam International Center for Theoretical Physics (see http://www.ictp.trieste.it/) and the european network "DYGLAGEMEM" (see http://chimera.roma1.infn.it/dyglagemem.html).
The directors were : M. Marsili (Trieste), M. Mezard (Orsay), F. Ricci-Tersenghi (Roma), R. Zecchina (Trieste).
Abstract of this school and conference:
One of the main trends of statistical physics in the last two decades has been the emergence of new concepts and techniques to study disordered systems. These are systems where the elementary microscopic objects (whether they are for instance spins or particles or human beings) are distinct one from another, generally because they are frozen in some random places with random environments. This evolution, joined to the progresses in the study of out-of-equilibrium systems, has defined some new areas where statistical physics can potentially turn out to be very useful. This activity focuses on the use of statistical physics to study complex systems in realms that are at the borderline of physics.
There is a number of research areas outside the traditional frontiers of physics where the application of these methods looks particularly promising. They all relate in some way to the collective behavior of heterogeneous agents, where ``agents'' can be as diverse as logical constraints in optimization problems or error correcting codes, proteins in molecular networks, or economic agents. The coherence of our approach derives from the concepts and techniques which are used and from the types of questions that we will address in all these different topics.
The school and conference aims at bringing together statistical physicists involved in interdisciplinary research and experts from computer science, bio-informatics, economics and game theory who share an interest in the same problems.


TRAINING SCHOOL and MEETING 2005:
We have organized, together with the EC network 'DYGLAGEMEM' a "Les Houches" winter school and meeting, from January, Monday the 31st, 2005 to February, Friday the 4th, 2005.


TRAINING SCHOOL and MEETING 2006
We are organizing, together with the EC network 'DYGLAGEMEM' a "Les Houches" winter school and meeting, from February 20, 2006 to February 24, 2006.
The meeting will have the role both of a school and of an active workshop. It will be based on five courses plus some short seminars, mainly given by young participants. The meeting will be open to all researchers: priority will be given to members of DYGLAGEMEM and STIPCO, but if possible (the limitation being the number of people that can be allowed in the Les Houches classrooms) also researchers not belonging to the networks will be accepted.
Details and applications (before december 19)


SUMMER SCHOOL 2006
We are co-organizing a main summer school in Les Houches during the whole month of july 2006. Attendance from the post-docs and students within the STIPCO network is particularly welcome. See details and application forms in:

SCIENTIFIC RESULTS

RESULTS OBTAINED IN 2003-2004:
1) Combinatorial optimization problems. We have made significant progress on the statistical physics studies of phase transitions in large scale combinatorial optimization problems: the phase diagrams of K-satisfiability, XOR-SAT and coloring have been studied in details, as well as the geometrical structure of the space of solutions. The dynamical behaviors (average running times) of standard algorithms has been studied. The dynamical polynomial/exponential transition in the random satisfiability and graph coloring problems has been shown to present some universal, algorithm independent, universality. A new algorithmic strategy based on message passing procedures has been developed and is being gradually improved, both for finding satisfiable configurations and for minimizing the number of violated constraints. In the reverse direction, algorithms borrowed from computer science have been used to study clustering properies of low energy configurations in spin glasses, as well as for the exact computation of the partition function in these problems. We have developed the study of dynamical transitions in physical systems, a basic effort which should help understanding dynamical transitions in algorithms. New results have been obtained on the dynamics of kinetically constrained interacting particles and on the out-of-equilibrium and long time properties of disordered systems.
2) Error correcting codes. We have made some progress in improving code constructions by devising an efficient algorithm for the removal of short loops. The performances of LDPC codes have been analyzed, and the average error probability and reliability exponents of regular LDPC codes have been obtained. We have shown how to use statistical physics methods in order to obtain rigorous lower bounds on the conditional entropy of messages encoding through random sparse-graph codes, and we have proved a finite-size scaling law for iterative coding systems.We have defined and analyzed a new list decoding algorithm which builds upon iterative decoding ideas and show their connection to maximum likelihood decoding.
3) Biological Systems. We have developed analytical and numerical tools for the study of networks and phylogenies, and applied them to the phylogenies of the influenza virus and the regulatory network of E. coli. We have developed a new method for discovering the binding sites of DNA-binding proteins, such as transcription factors. We have developed an antigen micro-array chip to study autoimmune diseases. The chip provides a "fingerprint" of the subject's immune system which we analyze with a sophisticated bio-informatics procedure. We have initiated the study of genome-wide network data, in particular co-expression data of genes. Related progress has been made in the study of regulatory evolution of the human HIV virus, where we have developed a method to predict the fitness of viral subtypes on the basis of sequence analysis We have given a detailed study of DNA unzipping, and of the RNA unfolding experiments by a mechanical force (single molecule experiments). We have studied the force-induced unfolding of random disordered RNA or single-stranded DNA polymers. The system undergoes a second order phase transition from a collapsed globular phase at low forces to an extensive necklace phase with a macroscopic end-to-end distance at high forces. We have studied the thermodynamic and dynamic behaviors of twist-induced denaturation bubbles in a long, stretched random sequence of DNA. We have also analyzed the condensation of DNA molecules and polyaminoamide dendrimer particles studied using laser tweezers.
4) Interacting agents in financial markets and socio-economic systems. We have generalized simple models of financial markets (Minority Game) in order to turn them into agent based market models. These generalized models, including the mixed Minority-Majority Game, the inclusion of contrarian and trend-following strategies, are able to explain known statistical anomalies of financial series and to capture bubble phase of financial markets. We have established the existence of negative, causal correlations between past price changes and future volatilities in stock markets. Using high frequency, trade by trade data, we have uncovered an interesting and hitherto unnoticed complexity of financial markets: a competition between liquidity takers, that create long range correlations by dividing their trading volume in small quantities, and liquidity providers that tend to mean revert the price such as to optimize their gains is at the origin of a subtle balance leading ]to a diffusive behaviour of the price. We have introduced a stiff `string' model for the fluctuations of the forward rate curve, whose predictions are in very good agreement with observations. We have studied the statistics of stock-order books. We have also studied other socio-economic systems: a model of urban traffic, the emergence of consensus in an interacting population, the problem of information retrieval in a connected network. We have also studied how well financial analysts forecast the earning of companies, on a very large data set. We confirm that financial analysts are on average over-optimistic and show a pronounced herding behaviour: they agree with each other five times more than with the actual result.