STATISTICAL AND COMPUTATIONAL THRESHOLDS IN SPIN GLASSES AND GRAPH INFERENCE PROBLEMS

自旋玻璃和图推理问题的统计和计算阈值

• 批准号: 2347177
• 负责人: Nike Sun
• 金额: $ 39.59万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-09-01 至 2027-08-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2347177&HistoricalAwards=false
• 关键词: STATISTICAL; COMPUTATIONAL; THRESHOLDS; SPIN; GLASSES

This research concerns large systems whose constituent components undergo simple interactions, such as nearest-neighbor constraints, leading to more complex aggregate behaviors, such as phase transitions. Systems that naturally exhibit long-range dependencies are of particular interest. A basic goal of the work is to develop new methods to analyze such dependencies, and thereby to characterize typical behaviors of large complex systems. A longer-term goal is to connect our understanding of static behaviors to algorithmic limits in high-dimensional computational and inference problems.The project has two main components. The first considers questions on phase transitions in random graph inference problems, both statistical and computational. The second will investigate statistical and algorithmic limits in random optimization problems, specifically in the context of mean-field spin glass models and random constraint satisfaction problems (CSPs). Postdoctoral researchers, graduate and undergraduate students will all be involved in the research.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.

这项研究涉及大型系统的组成部分经历了简单的相互作用，例如最近的邻居限制，从而导致更复杂的骨料行为，例如相变。自然表现出长期依赖性的系统特别感兴趣。这项工作的一个基本目标是开发新方法来分析此类依赖性，从而表征大型复杂系统的典型行为。一个长期的目标是将我们对静态行为的理解与高维计算和推理问题中的算法限制联系起来。该项目具有两个主要组成部分。第一个考虑了关于统计和计算的随机图推理问题中有关相变的问题。第二个将在随机优化问题中研究统计和算法限制，特别是在平均场自旋玻璃模型和随机约束满意度问题（CSP）的背景下。博士后研究人员，研究生和本科生都将参与研究。该奖项反映了NSF的法定任务，并且使用基金会的知识分子优点和更广泛的影响审查标准，被认为值得通过评估来获得支持。