STATISTICAL AND COMPUTATIONAL THRESHOLDS IN SPIN GLASSES AND GRAPH INFERENCE PROBLEMS

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.