Learning over Structured
High-Dimensional Objects:
Theory and Complexity
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.
The CIMPA and the Bernoulli Center collaborate to fund the participation of young researchers, including doctoral students and those who have completed their doctorate within the last 5 years or are under the age of 36. This opportunity is aimed at individuals based in developing countries, as defined by the IMU-CDC. You can find more information and how to apply on this page.
