A Proposal for Research on Markov Chains, Approximate Counting and Finite Metric Spaces

关于研究马尔可夫链、近似计数和有限度量空间的建议这个项目包含三个松散相关的主题：马尔可夫链的计算应用、近似计数和有限度量空间的算法影响。在过去的十年中，所谓的“马尔可夫链蒙特卡罗方法”已经成为一种强大的算法范例，在近似计数、统计物理和组合优化等领域具有广泛的应用。PI正在以下三个方向推进这些应用：开发基于多商品流的新技术来分析几何马尔可夫链(其中状态空间是凸体内的整点集合)。研究切比雪夫加速等技术，其潜在地可以修改马尔可夫链以显著加快其收敛。改进对某些马尔可夫链在物理系统构型上的快速混合性质与这些系统的热力学性质之间新出现的联系的理解。与最近旨在根据其逼近程度对NP-Hard优化问题进行分类的活动相平行，非政府组织对#P--难以计数问题的类似分类作出了贡献。这里的具体目标包括：研究逼近恒等式这一中心问题的新算法。发展计数问题之间的近似保持约简，以便，例如，可以构造一类等价于永久的问题。有限度量空间提供了一种干净而优雅的范例，它捕获(并经常简化)了几个以前特别的算法思想。该项目的第三部分涉及对有限度量的系统研究，具体地说：设计新的L1嵌入技术，无论是在一般情况下(以在最优的o(Logn)内实现失真)还是对于特殊度量(例如平面图上支持的那些度量)。这在算法上有应用，其中包括近似网络中最稀疏割的中心问题。改进的嵌入到低维空间的技术的发展。这些算法可应用于解决无处不在的问题，如最近邻搜索和聚类。用较简单的度量逼近复杂的度量。这将使适用于简单指标(如树)的现有算法得到更广泛的应用。

A Proposal for Research on Markov Chains, Approximate Counting and Finite Metric Spaces Alistair Sinclair University of California, BerkeleyThis project contains three loosely related themes: computational applications of Markov chains, approximate counting, and algorithmic apects of finite metric spaces.During the past decade, the so-called "Markov chain Monte Carlo method" has emerged as a powerful algorithmic paradigm, with applications in such areas as approximate counting, statistical physics and combinatorial optimization. The PI is pushing ahead with these applications, in the following three directions:Development of new techniques based on multicommodity flow to analyze geometric Markov chains (where the state space is the set of integer points inside a convex body).Investigation of techniques such as Chebyshev acceleration, which can potentially modify a Markov chain so as to substantially speed up its convergence.Improved understanding of newly emerging connections between the rapid mixing property of certain Markov chains on the configurations of physical systems and the thermodynamic properties of those systems.In parallel with recent activity aimed at classifying NP-hard optimization problems according to their degree of approximability, the PI is contributing to a similar classification of #P-hard counting problems. Specific aims here include:Investigation of novel algorithms for the central problem of approximating the permanent. Development of approximation-preserving reductions between counting problems so that, for example, a class of problems that are equivalent to the permanent can be constructed.Finite metric spaces provide a clean and elegant paradigm that captures (and often streamlines) several previously ad hoc algorithmic ideas. The third part of the project involves a systematic study of finite metrics, and specifically:The design of new techniques for l1 embedding, both in the general case (to achieve a distortion within o(log n) of optimal) and for special metrics (such as those supported on planar graphs). This has algorithmic applications to, among others, the central problem of approximating the sparsest cut in a network.Development of improved techniques for embeddings into low-dimensional spaces. These have applications to algorithms for ubiquitous problems such as nearest-neighbor searching and clustering.Approximation of complex metrics by simpler ones. This would allow existing algorithms that work well for simple metrics (such as trees) to be applied more widely.