Collective Dynamics in Information systems

Date :From 2008-03-01 To 2008-04-15
Advisory committee :
Local coordinators :DI Zengru,HAN Jing,TANG Leihan, XU Ke, ZHOU Haijun
International coordinators :Erik Aurell,Mikko Alava,Sui Huang,Haijun Zhou,Terry Hwa

In the last years there has been great interest in applications of statistical physics to information systems, as witnessed by no less than four satellite meetings to the Statphys 23 congress (July 2007). The emergent, collective aspects that are of interest here range from the traffic on the Internet or in Peer-to-Peer networks, to the structure and solution of hard optimization problems to analogies in bioinformatics.
Work by physicists in this novel field has lead to some recent advances such as the 'Survey Propagation' algorithm for hard NP-complete optimization problems, and its fundamental understanding via the cavity method of spin glasses. A related example is the 'Belief Propagation' method and its applications to decoding, which have been elucidated by statistical mechanics techniques and analogues.

The Internet itself is an example of a disordered, scale-free graph and the spreading of epidemics in such conditions was first shown by statistical physicists to be fundamentally different from the usual paradigm since in many cases the spreading threshold vanishes. The control and self-generated collective dynamics of many interacting agents or markets is becoming ever more topical due to the proliferation of Peer-to-Peer technologies.

Within this general frame-work the program will address:

The relationship between static characteristics of combinatorial optimization and satisfiability problems and dynamical processes to solve these.
Initially, it was believed that the clustering transition in e.g. satisfiability problems heralds a phase where problems are solvable but hard to solve. Research over the last couple of years has shown that this is not necessarily the case. Some heuristics, e.g. stochastic search procedures to find solutions, work effectively on large problems well inside the clustered phase, while others fail to find solutions efficiently in the unclustered phase.

Understanding these heuristics and, in general, non-equilibrium dynamics of glasses, including spin glasses, is a fundamental problem of statistical physics, and is of great current interest in applied combinatorial optimization. Advances in this area has outstanding application potential as satisfiability and combinatorial problems are ubiquitous in planning, scheduling, large-scale design, and other engineering fields.

Living cells and living organisms are information processing systems. While some systems are centralized and depend on a central clock circadian rhythms, most are naturally distributed. Examples include most neural processing, quorum sensing, most actions of gene regulation, and more.

The collective behavior of independent, interacting agent systems is a highly topical issue both as regards the design and control of e.g. P2P networks and traffic on networks, such as the Internet. Issues one deals with are ``optimality'' and ``congestion'' and the question of optimal cooperation, or in the game-theoretical language of Nash equilibria.

Please go to: to find our main page