Many modern, large-scale datasets are structured as graphs, matrices, tensors, and other combinatorial objects. A central challenge across mathematics, statistics, and theoretical computer science is to understand the limits of inference, when these limits can be achieved computationally, and where fundamental barriers arise.
Recent progress has provided evidence of computational-statistical gaps in many such problems. Low-degree polynomials, Sum-of-Squares, the overlap gap property, and other signatures of hardness, together with average-case reductions, have emerged as powerful frameworks for studying these questions in random models with planted structure. These developments have sharpened our understanding of computational phase transitions while also raising fundamental questions about the scope and limitations of existing techniques.
This six-week program will bring together leading and early-career researchers working on high-dimensional inference, random graphs and graphons, random matrices and tensors, average-case complexity, and related topics. It will feature two workshops and a PhD course, complemented by seminars, reading groups, and collaborative working sessions
Organizers: Fiona Skerman, Uppsala University - Anda Skeja, Uppsala University