AF: Small: Markov Chain Algorithms for Problems from Computer Science and Statistical Physics

基于马尔可夫链的采样算法被广泛应用于科学领域，主要用于近似计数、组合优化和建模。这些算法使用随机漫步来探索一个大的状态空间，确定它们的收敛时间通常是建立许多使用随机抽样的近似算法效率的关键步骤。这个项目的主要目标是确定适合这种方法的问题，设计可证明有效的算法，并开发概率技术来实现这种分析。对于这些目标中的每一个，计算机科学都受益于相关领域的见解，特别是统计物理学和离散概率。该项目探讨了物理系统的相变和局部马尔可夫链的收敛率之间的紧密联系，以解释各种自然采样方法的局限性。这种对应关系也指导我们通过允许非局部移动或在修改状态空间上设计马尔可夫链来搜索更有效的算法。本PI将探索这两个方面，通过在相变两侧的有效和非有效制度中设计更强的分析方法，并在局部算法被证明过于缓慢时寻找替代的非局部算法进行采样。要探索的应用包括统计物理学中的核心模型、经济学中的谢林隔离模型、规划和设计中的几何抽样问题，以及输入有噪声或随时间变化的数据科学中的抽样问题。这项跨学科工作的广泛影响有许多方面，特别是通过将一个领域的见解带到另一个领域来连接科学领域。PI定期向各领域的学生和教师进行技术和调查讲座，指导一个跨学科研究中心，并组织研讨会和会议，包括来自不同学科的参与者。研究结果通过讲座、出版物传播，并将在网站上公布。PI继续大力倡导女性在学术界的地位，包括担任高级计算机教授，参与公平小组，向广泛的女性群体发表演讲，并为女性博士生提供建议。

Sampling algorithms based on Markov chains are used across the sciences, primarily for approximate counting, combinatorial optimization and modeling. These algorithms use random walks to explore a large state space, and determining their convergence time is typically the critical step for establishing the efficiency of many approximation algorithms using random sampling. The primary goals of this project are identifying problems amenable to this approach, designing provably efficient algorithms, and developing probabilistic techniques to enable such analyses. For each of these goals, computer science benefits from insights from related fields, especially statistical physics and discrete probability.The project explores strong connections between phase transitions of physical systems and convergence rates of local Markov chains to explain the limitations of various natural approaches to sampling. This correspondence also guides our search for more efficient algorithms by allowing nonlocal moves or designing Markov chains on modified state spaces. This PI will explore both aspects, by designing methods from stronger analysis in the efficient and non-efficient regimes on both sides of the phase transition, and by searching for alternative non-local algorithms for sampling when local algorithms have been proven to be prohibitively slow. Applications to be explored include the hard-core model from statistical physics, the Schelling model of segregation from economics, geometric sampling problems form planning and design, and sampling problems from data science where inputs are noisy or evolving over time.The broader impacts of this interdisciplinary work have many facets, especially for bridging scientific fields by bringing insights from one field to another. The PI regularly gives technical and survey talks to students and faculty across fields, directs an interdisciplinary research center and organizes workshops and conferences including participants from disparate disciplines. The results disseminated by talks, publications and will be made accessible on websites. The PI continues to be a strong advocate for women in academia, including serving as the ADVANCE Professor of Computing, participating on equity panels, presenting lectures to broad groups of women, and advising women Ph.D. students.