Approximate Counting, Markov Chains and Phase Transitions

近似计数、马尔可夫链和相变

• 批准号: 1540286
• 负责人: Richard Karp
• 金额: $ 2.5万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-01 至 2016-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1540286&HistoricalAwards=false
• 关键词: Approximate; Counting; Markov; Chains; Phase

Markov chains play an important role in a variety of fields, but the analysis of their convergence properties remains a challenging problem. The emphasis of this workshop is on the analysis of "large" Markov chains, i.e., finite-state chains where the number of states is exponentially large as a function of the description size of an individual state. Such chains are especially important in the study of statistical physics models and the design of approximate counting algorithms. The workshop will bring together researchers in the analysis of large Markov chains from many areas of application, to review progress and to identify challenges for future research.Recently there has been considerable success in designing approximate counting algorithms without the use of Markov chains, relying instead on so-called "spatial mixing" properties. Remarkably, matching hardness results have been established in the special case of antiferromagnetic 2-spin systems. This beautiful collection of results ties together the complexity of approximate counting on a general class of graphs with an associated phase transition for the infinite regular tree. By highlighting recent results in the study of approximate counting problems, the workshop will explore analogous connections for other models and for related problems. Video tapes of presentations and discussions will be distributed to the public. Students will be encouraged to participate in this interdisciplinary area.

马尔可夫链在许多领域中发挥着重要作用，但其收敛性的分析仍然是一个具有挑战性的问题。本次研讨会的重点是对“大”马尔可夫链的分析，即，有限状态链，其中状态的数量作为单个状态的描述大小的函数呈指数级大。这种链在统计物理模型的研究和近似计数算法的设计中特别重要。研讨会将汇集来自许多应用领域的大型马尔可夫链分析研究人员，审查进展并确定未来研究的挑战。最近，在设计近似计数算法方面取得了相当大的成功，而不使用马尔可夫链，而是依赖于所谓的“空间混合”属性。值得注意的是，在反铁磁2-自旋系统的特殊情况下，已经建立了匹配的硬度结果。这个美丽的结果集合将近似计数的复杂性与无限正则树的相关联的相变联系在一起。通过强调近似计数问题研究的最新成果，研讨会将探讨其他模型和相关问题的类似联系。 发言和讨论的录像带将向公众分发。 将鼓励学生参与这一跨学科领域。