CAREER:Phase Transitions in Algorithms, Complexity, and Geometry

吉布斯测度（或玻尔兹曼分布）起源于统计力学，用于模拟物质的相位，但由于其对复杂依赖关系的简单编码，因此在统计学，机器学习，编码理论和数学物理学中找到了许多实际应用。 与吉布斯测度相关的两个算法任务在应用中是必不可少的：从给定模型中采样并有效地近似其归一化常数，即配分函数。 本项目旨在阐明基础统计物理模型中的相变与这两个问题的计算复杂性之间的联系。 该项目的特点是一个综合的研究和教育计划，与推进吉布斯措施的基础知识和改善跨学科的数学教育的互补目标。该教育计划有针对三个层面的活动：向高中生介绍数学研究的外联讲习班;为本科生教师创建实施有效教学技术的工具;以及开发跨学科统计物理应用的新研究生课程。更具体地说，这项研究有三个主要目标。 首先，发展有效的采样算法吉布斯措施在低温下，相共存制度的模型与有限数量的基态。 第二，使统计物理学中强大但不严格的空腔方法成为理解随机计算问题的算法易处理性的严格数学工具。 第三，通过利用统计物理学的工具和见解来理解高维中的基本几何对象-球体填充，球体覆盖和球形代码。 这三个目标的追求将在计算机科学、统计学和组合学中引入新的概率方法。该奖项反映了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.