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的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。