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.