EMT/MISC: Collaborative Research: Harnessing Statistical Physics for Computing and Communication

点击翻译按钮获取中文摘要

This project exploits methods from statistical physics to provide fundamental advances in computing and communication systems. The intersection of computer science, information theory and statistical physics has seen a recent explosion of activity, resulting in new algorithms and new methods of analysis. Discrete computational challenges including constraint satisfaction, error correction and control of massive networks have benefited from techniques and insights offered by statistical physics. Physics, at the same time, has been significantly enriched by approaches from discrete computation, such as message-passing algorithms. The investigators study two complementary approaches for addressing algorithmic challenges: 1) treating problem instances as members of a random ensemble that can be analyzed as a physical model, and 2) identifying specific classes of instances amenable to physical analysis. The first suggests a fundamental connection between algorithmic performance and an underlying physical phase structure, and has already led to significant new algorithms for unstructured random graphs or networks. The challenge is to generalize it to structured cases. The second uses techniques such as renormalization group and multiscale decomposition, and is proving to be a powerful new approach in probabilistic inference.