AF: Small: Markov Chains, Statistical Physics, and Mobile Geometric Graphs

该项目有三个主要主题：1。马尔可夫链蒙特卡罗算法：研究基于马尔可夫链的提升加速算法的技术，以及对马尔可夫链的分析——用于点阵三角剖分和随机聚类模型——超出当前技术范围的技术。统计物理与计算：继续研究自旋系统的Glauber动力学，特别关注边界条件对混合时间的影响这一关键开放问题；利用对空间混合的新兴理解，为计数和采样问题推导新的算法和复杂性结果；物理学中玻尔兹曼方程分析新技术在群体遗传学和遗传算法非线性模型计算研究中的应用。移动几何图形：对将移动节点引入无线网络模型的影响进行了数学上严格的调查——从增加的功率和新的算法挑战两方面来看。主题之间的大量联系提供了思想上的连贯性。例如，通过格劳伯动力学，马尔可夫链在统计物理学中发挥着核心作用；相变和阈值现象出现在所有三个主题中，正如系统随时间动态演化的普遍概念一样；对可移动几何图形的理解与物理学中的连续体渗流密切相关。此外，这三个主题都是从理论计算机科学延伸到其他学科的例子，特别是概率论、统计物理和无线网络，该项目预计将有助于计算机科学和这些领域之间的交叉施肥。在整个项目中，研究问题的选择不仅受到其内在意义的驱动，而且受到它们对现有技术的挑战以及它们与其他领域的联系的程度的驱动。

The project has three main themes: 1. Markov chain Monte Carlo algorithms: The study of techniques such as lifting to speed up algorithms based on Markov chains, as well as the analysis of Markov chains---for lattice triangulations and the random cluster model---that are beyond the range of current techniques.2. Statistical physics and computation: A continuing study of the Glauber dynamics for spin systems, focusing especially on the key open question of the influence of boundary conditions on the mixing time; the harnessing of an emerging understanding of spatial mixing to derive new algorithms and complexity results for counting and sampling problems; the application of new techniques for the analysis of the Boltzmann equation in physics to a computational study of nonlinear models in population genetics and genetic algorithms.3. Mobile geometric graphs: A mathematically rigorous investigation of the effects -- in terms of both increased power and novel algorithmic challenges -- of introducing mobile nodes into models of wireless networks.Numerous connections among the themes provide intellectual coherence. For example, Markov chains play a central role in statistical physics through the Glauber dynamics; phase transitions and threshold phenomena appear in all three themes, as does the pervasive notion of dynamical evolution of a system over time; and the understanding of mobile geometric graphs is intimately connected with continuum percolation in physics.In addition, all three themes are examples of outreach from theoretical computer science to other disciplines, notably probability theory, statistical physics and wireless networking, and the project is expected to contribute to cross-fertilization between computer science and these fields. Throughout the project, the choice of research questions is driven not only by their intrinsic significance but also by the challenges that they present to existing techniques and the extent to which they illuminate connections with these other fields.