Statistical Mechanics of Distributed Information Systems

15 Jul 2007, 16:15 → 18 Jul 2007, 20:00 Europe/Stockholm

Erik Aurell (KTH), John Hertz (NORDITA), Mikko Alava (HUT), Scott Kirkpatrick (HUJI), Supriya Krishnamurthy (SICS)

THIS MEETING IS NOW OVER

The organizers thank NORDITA , The Academy of Finland and the KTH ACCESS Linnaeus Center for financial support

For final scientific program, contributions and participants, follow the links to the left. For the next events in this series, welcome to CDInfos0803 in Beijing, China, and to PhysDIS in Stockholm, Sweden.

Sunday 15 July

16:15 → 18:30 Opening session

16:15 Multi-cellular Logic Circuits

Speaker: Prof. Jonathan Yedidia (Mitsubishi Electric)

Slides Yedidia_multicellular_logic_circuits.pdf

17:15 break

17:30 Principles of Multicellular Life: Complex genetic networks and cell fate decisions

Speaker: Prof. Sui Huang (Harvard)

Slides Huang-small.pdf

Monday 16 July

09:00 → 12:30 Decoding dynamics

09:00 ML decoding via mixed-integer adaptive linear programming

Speaker: Prof. Jonathan Yedidia (Mitsubishi Electric)

Slides Yedidia_ML_decoding.ppt

10:00 break

10:30 Fountain Codes

Speaker: Prof. Amin Shokrollahi (EPFL)

Slides Shokrollahi-fountain.pdf

11:30 Loop Calculus for Graphical Models of Statistical Inference

Loop Calculus introduced in [Chertkov, Chernyak '06] constitutes a new theoretical tool that expresses explicitly the symbol Maximum-A-Posteriori solution of a general statistical inference problem via a solution of the Belief Propagation, or Bethe-Pieirls, equations. This finding brought a new significance to the BP concept, which in the past was thought of as just a loop-free approximation. In this presentation I will explain main concept, algorithmic implications and feature challenges of the Loop Calculus approach.

Speaker: Prof. Misha Chertkov (LANL)

Slides chertkov.pdf

15:00 → 18:00 Biological distributed information systems

15:00 Non-Genetic Cell Heterogeneity: Mutationless evolution in Cancer?

Speaker: Prof. Sui Huang (Harvard)

16:00 break

16:30 Evolutionary games in finite populations

Speaker: Dr Arne Traulsen (Harvard)

Slides Traulsen_EvoGames.pdf

17:30 Exact Asymptotic Results for the Bernoulli Matching Model of Sequence Alignment

Finding analytically the statistics of the longest common subsequence (LCS) of a pair of random sequences drawn from c alphabets is a challenging problem in computational evolutionary biology. We present exact asymptotic results for the distribution of the LCS in a simpler, yet nontrivial, variant of the original model called the Bernoulli matching (BM) model. We show that in the BM model, for all c, the distribution of the asymptotic length of the LCS, suitably scaled, is identical to the Tracy-Widom distribution of the largest eigenvalue of a random matrix whose entries are drawn from a Gaussian unitary ensemble.

Speaker: Prof. Sergey Nechaev (CNRS)

Slides Nechaev_talk.pdf

Tuesday 17 July

09:00 → 12:30 Heuristics and average hardness

09:00 Understanding Search Trees via Statistical Physics

Speaker: Prof. Satya Majumdar (CNRS)

Slides Majumdar.pdf

10:00 break

10:30 Two inverse problems inspired from biophysics

Speaker: Prof. Remi Monasson (CNRS)

11:30 Barriers and local minima in energy landscapes

Speaker: Prof. Petteri Kaski (HIIT, Helsinki)

Slides Kaski.pdf

15:00 → 19:00 Overlays, analysis and properties

15:00 Integrating geographical, technological and economical factors in a model of Internet growth

Speaker: Dr Petter Holme (U New Mexico)

Slides Holme_internet.pdf Holme_social.pdf

16:00 break

16:30 Interacting traders with public and private information (statistical mechanics perspective)

Speaker: Prof. Andrea De Martino (Rome)

Slides DeMartino_aaland.pdf

17:30 break

18:00 Criticality and Phase Transitions in Diversity Colouring

Speaker: David Saad (Aston University Birmingham)

Slides Saad_SMDistStorage.pdf

18:30 Probability Collectives: A practical information theoretic prescriptive on bounded rational game theory and statistical physics

In this short presentation an exposition is made of the ideas put forth by David H. Wolpert connecting Bounded rational Game Theory with Statistical Physics concepts by means of Information Theory. The mathematical structure that is used, know as Product Distribution (PD) theory, plays a central role in a framework for learning and optimization that is called Probability Collectives PC. We demonstrate the veracity of PC in a number of applications.

Speaker: Prof. Mohammed El-Beltagy

Slides ElBeltagy_probabilityCollectives.ppt

Wednesday 18 July

09:00 → 12:30 The cavity method: message passing beyond BP

09:00 The bridge from belief propagation to survey propagation

Speaker: Prof. Marc Mezard (CNRS)

10:00 break

10:30 The structure of constraint satisfaction problems

Speaker: Dr Elitza Maneva (IBM Almaden)

Slides Maneva.ppt

11:30 Coloring random regular graphs

Speaker: Dr Xavier Pérez (Technical University of Catalonia (UPC))

Slides xavier_perez.pdf

12:00 Phase Transitions in Constraint Satisfaction Problems and Algorithmic Consequences

Speaker: Lenka Zdeborova (U Paris-Sud)

Slides Zdeborova.pdf

14:30 → 20:00 Student session, July 18

14:30 Random models vs Non random models

Speaker: Dr Massimo Ostili

Slides Ostilli.pdf

15:00 Temperature dependent sampling in random KSAT problems

Speaker: Mr John Ardelius

15:20 break

15:30 Belief Propagation in Wireless Sensor Networks

Speaker: Ms Bracha Hod (HUJI)

16:00 GODS: Global Observatory for Distributed Systems

Speaker: Mr Cosmin Arad

GODS: Global Observatory for Distributed Systems GODS.ppt

16:20 break

16:30 Prediction and Identification of non-coding RNA in Bacteria

Speaker: Mr Aymeric Fouquier d'Herouel (KTH Computational Biology)

17:00 Comparing mRNA- and protein expression

Speaker: Mr Gabriel Östlund (SBC, Stockholm University)

17:20 break

17:30 A Graph Partitioning Algorithm on the Planted Partition Model

Speaker: Mr Mikael Onsjö (CS Chalmers University of Technology)

Paper http://www.odinlake.net/Publications/GraphPartitioning_proc.pdf

Slides onsjoe07mariehamn.pdf

17:50 Domain tree based analysis of protein architecture evolution

Speaker: Mr Kristoffer Forslund

Abstract domain.abstract.pdf

18:10 break

18:20 Statistical Physics of LDPC Codes on Real MIMO Channels

Speaker: Dr Roberto Castro Alamino

Paper 0705.1644.pdf http://arxiv.org/abs/0705.1644

Slides Aland_2007.pdf

18:50 Cycle avoidance in LDPC codes

Speaker: Mr Mattias Andersson (S3 KTH)

19:10 break

19:20 Multi-user detection with sparse signature codes

Speaker: Mr Jack Raymond

Paper http://arxiv.org/abs/0704.0098

Slides MDwCDMA2.pdf

19:40 Distributed Source Coding in Audio Coding

Speaker: Mr Minyue Li

Slides finland_July_18.ppt