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

AF：小：马尔可夫链、统计物理和移动几何图

• 批准号: 1016896
• 负责人: Alistair Sinclair
• 金额: $ 49.81万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-01 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1016896&HistoricalAwards=false
• 关键词: AF; Small; Markov; Chains; Statistical

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.

该项目具有三个主要主题：1。MarkovChain Monte Carlo算法：基于马尔可夫链加快算法的技术的研究，以及对马尔可夫链的分析 - 用于晶格三角形和随机群集模型---超出了当前技术的范围2。统计物理和计算：对旋转系统的GLAUBER动力学的持续研究，尤其重点是边界条件对混合时间的影响的关键开放问题；利用对空间混合的新兴理解来得出新的算法和复杂性结果，以实现计数和抽样问题；新技术在物理学中的玻尔兹曼方程分析中的应用在人群遗传学和遗传算法中非线性模型的计算研究中。3。移动几何图形：对效果的数学严格研究 - 就功率增加和新颖的算法挑战而言，将移动节点引入无线网络模型中。主题之间的连接提供了智力上的连贯性。 例如，马尔可夫链通过Glauber动力学在统计物理学中起着核心作用。相变和阈值现象出现在所有三个主题中，随着时间的推移，系统动态演变的普遍概念也是如此。对移动几何图的理解与物理学中的连续性渗透密切相关。此外，这三个主题都是从理论计算机科学到其他学科的外展的示例，尤其是概率理论，统计物理和无线网络，并且预计该项目有望有助于计算机科学与这些领域之间的交叉施肥。 在整个项目中，研究问题的选择不仅是由于它们的内在意义而驱动的，而且还取决于他们对现有技术的挑战以及它们照亮与其他领域的联系的程度。