STATISTICAL AND COMPUTATIONAL THRESHOLDS IN SPIN GLASSES AND GRAPH INFERENCE PROBLEMS

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

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.