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

基于马尔可夫链的抽样算法广泛应用于科学领域，主要用于近似计数、组合优化和建模。这些算法使用随机游动来探索大的状态空间，而确定它们的收敛时间通常是建立许多使用随机采样的近似算法的效率的关键步骤。这个项目的主要目标是找出适合于这种方法的问题，设计被证明有效的算法，并开发概率技术来实现这种分析。对于这些目标中的每一个，计算机科学都受益于相关领域的见解，特别是统计物理和离散概率。该项目探索了物理系统的相变和局部马尔可夫链的收敛速度之间的密切联系，以解释各种自然抽样方法的局限性。这种对应关系还通过允许非局部移动或在修改的状态空间上设计马尔可夫链来指导我们寻找更有效的算法。这一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.