CAREER:Phase Transitions in Algorithms, Complexity, and Geometry

吉布斯测量(或称玻尔兹曼分布)起源于统计力学，用于对物质的相进行建模，但由于其对复杂依赖关系的简单编码，因此在统计学、机器学习、编码理论和数学物理中得到了大量的实际应用。与Gibbs度量相关的两个算法任务在应用中是必不可少的：从给定的模型中采样，并有效地逼近其归一化常数，即配分函数。该项目旨在阐明基本统计物理模型中的相变与这两个问题的计算复杂性之间的联系。该项目以综合研究和教育计划为特色，具有促进吉布斯措施的基本知识和改善跨学科数学教育的补充目标。该教育计划有三个层次的活动：向高中生介绍数学研究的外联讲习班；为本科生教师创建工具，以实施有效的教学技术；以及开发新的研究生课程，使其在统计物理在各学科中的应用。更具体地说，这项研究有三个主要目标。首先，针对基态数目有限的模型，提出了低温、相共存条件下Gibbs测量的有效采样算法。第二，将统计物理学中强大但非严格的空腔方法变成一种严格的数学工具，用于理解随机计算问题的算法处理能力。第三，通过利用统计物理学的工具和见解，理解高维的基本几何对象-球面填充、球面覆盖和球面代码。对这三个目标的追求将在计算机科学、统计学和组合学中引入新的概率方法。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Gibbs measures (or Boltzmann distributions) originated in statistical mechanics to model the phases of matter, but have since found numerous practical applications in statistics, machine learning, coding theory, and mathematical physics due to their simple encoding of complex dependencies. Two algorithmic tasks associated to Gibbs measures are essential in applications: sampling from a given model and efficiently approximating its normalizing constant, the partition function. This project aims to elucidate the connection between phase transitions in the underlying statistical physics model and the computational complexity of these two problems. The project features an integrated research and education plan, with the complementary goals of advancing fundamental knowledge of Gibbs measures and improving interdisciplinary mathematical education. The educational plan has activities aimed at three levels: outreach workshops to introduce high school students to mathematical research; the creation of tools for undergraduate instructors to implement effective pedagogical techniques; and the development of new graduate courses in applications of statistical physics across disciplines. More specifically, the research has three main goals. First, to develop efficient sampling algorithms for Gibbs measures in the low temperature, phase coexistence regime for models with a bounded number of ground states. Second, to make the powerful but non-rigorous cavity method from statistical physics into a rigorous mathematical tool for understanding the algorithmic tractability of random computational problems. Third, to understand fundamental geometric objects in high dimensions -- sphere packings, sphere coverings, and spherical codes -- by utilizing tools and insights from statistical physics. The pursuit of these three goals will introduce new probabilistic methods in computer science, statistics, and combinatorics.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.