Le prochain Mokameeting aura lieu le mercredi 26 février 2020 à INRIA Paris (2 rue Simone Iff) en salle Jacques-Louis Lions 1 à 14h00.
Nous aurons le plaisir d’écouter un exposé de Tim Kunisky (Courant Institute, New York University).
Titre : The low-degree method for identifying statistical-to-computational gaps
Résumé : I will give a pedagogical introduction to a technique for studying statistical-to-computational gaps, certain regimes in statistical inference problems where inference is, in principle, possible with unbounded computational resources, but various evidence suggests that efficient algorithms for inference do not exist. A recent and strikingly simple method for identifying those regimes analyzes when inference or hypothesis testing can be performed using low-degree polynomials. I will outline how to apply this technique to various problems, giving the ingredients of a simple “back-of-the-envelope” calculation that correctly predicts the difficulty of tasks ranging from principal component analysis in matrices and tensors to community detection in structured graphs.
Based loosely on a recent survey paper with Alex Wein and Afonso Bandeira:
https://arxiv.org/abs/1907.11636
