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.

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