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

EMT/MISC：合作研究：利用统计物理进行计算和通信

• 批准号: 0829861
• 负责人: Bart Selman
• 金额: $ 18.2万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0829861&HistoricalAwards=false
• 关键词: EMT; MISC; Collaborative; Research; Harnessing

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.

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