Scaling in Biological and Social Networks - Abstract - Chertkov
From Santa Fe Institute Events Wiki
| Workshop Navigation |
Physics of Algorithms: Loop Calculus for Graphical Models of Statistical Inference
Misha Chertkov (CNLS and Theory Division, LANL)
Problems in information processing are computationally complex at a fundamental level: the difficulty of solving the problem grows exponentially often making it completely intractable. Recently, properties of these computationally hard problems have been studied using approaches developed by physicists, leading to an intriguing convergence of themes from engineering and computer science with methods from statistical physics. Graphical models of statistical inference/reconstruction were in the focus of the synergy between the fields.
In this talk I will review a theoretical approach, coined loop calculus, which allows to express partition function of a general graphical model in terms of a series, where each term is associated with a loop on the graph. Algorithmic utility of this approach will be discussed on the enabling example of the belief propagation decoding of modern error-correction codes.