Approximate Counting, Statistical Physics and Computation

近似计数、统计物理与计算

• 批准号: 0635153
• 负责人: Alistair Sinclair
• 金额: $ 33万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-02-01 至 2011-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0635153&HistoricalAwards=false
• 关键词: Approximate; Counting; Statistical; Physics; Computation

AbstractThe project contains two main themes that are related in various ways:(1) approximation algorithms for counting problems, and (2) computational aspects of statistical physics. Counting problems arise in numerous application areas, including combinatorics, algebra, volume and integration, statistical physics, computational finance and statistical hypothesis testing. In almost all cases they are intractable in exact form; theme (1) of the project is focused on constructing efficient algorithms for these problems that guarantee any desired degree of approximation. Theme (2) of the project aims to better understand deep emerging connections between phase transitions in physical systems on the one hand, and computational complexity or the running time of algorithms on the other. The two themes are united by various algorithmic and mathematical techniques (notably, the Markov chain Monte Carlo paradigm). In addition, there is a focus in the project on the application of ideas from theoretical Computer Science to problems in other sciences.Specific goals of theme (1) include the following: to resolve the status of a number of important counting problems, either by developing efficient approximation algorithms or by proving them hard to approximate; to construct more efficient approximation algorithms for central problems in the field; and to explore novel application areas such as computational finance. Specific topics to be addressed within theme (2) include the mixing time of Glauber dynamics; the behavior of message-passing algorithms such as Belief Propagation; and connections between physical models and random constraint satisfaction problems.

摘要该项目包含两个以各种方式相关的主题：（1）计数问题的近似算法，以及（2）统计物理的计算方面。 计数问题出现在许多应用领域，包括组合学、代数、体积和积分、统计物理、计算金融和统计假设检验。 几乎在所有情况下，它们的精确形式都是难以处理的。该项目的主题 (1) 侧重于为这些问题构建有效的算法，以保证任何所需的近似程度。 该项目的主题（2）旨在一方面更好地理解物理系统中相变之间的深层联系，另一方面理解计算复杂性或算法的运行时间。 这两个主题通过各种算法和数学技术（特别是马尔可夫链蒙特卡罗范式）统一起来。 此外，该项目的重点是将理论计算机科学的思想应用于其他科学的问题。主题（1）的具体目标包括以下内容：解决许多重要计数问题的现状，或者通过开发有效的近似算法或证明它们难以近似；为该领域的中心问题构建更有效的近似算法；并探索计算金融等新的应用领域。 主题（2）中要讨论的具体主题包括格劳伯动力学的混合时间；消息传递算法的行为，例如置信传播；以及物理模型和随机约束满足问题之间的联系。