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

这个项目利用统计物理学的方法，在计算和通信系统中提供基本的进步。计算机科学、信息论和统计物理的交叉最近出现了爆炸性的活动，导致了新的算法和新的分析方法。离散的计算挑战，包括约束满足、纠错和大规模网络的控制，都受益于统计物理学提供的技术和见解。与此同时，离散计算的方法极大地丰富了物理学，例如消息传递算法。研究人员研究了两种解决算法挑战的互补方法：1)将问题实例视为可以作为物理模型进行分析的随机集合的成员，以及2)确定适合物理分析的特定类型的实例。第一个提出了算法性能和基本物理相结构之间的基本联系，并且已经导致了用于非结构化随机图或网络的重要的新算法。挑战在于将其推广到结构化案例。第二种方法使用了重整化群和多尺度分解等技术，是概率推理中一种强有力的新方法。

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.