On Friday, June 14, 11am, we have the pleasure of welcoming Christophe Giraud (Institut de Mathématiques d’Orsay), who will give a 90-minute seminar on « Information-computation gaps in high-dimensional clustering » (abstract below).
The seminar will take place in room 15-16-309 (salle de conference du LJLL).
Best regards,
Borjan & Raphaël, for the organizers
—————————————————————————————————————————————————
Speaker:
Christophe Giraud (Institut de Mathématiques d’Orsay)
Title:
Information-Computation gaps in high-dimensional clustering
Abstract:
The simple task of clustering a mixture of Gaussian appears to be challenging in high-dimension. In addition to the difficulties inherent to high-dimensional supervised classification, a computational barrier can preclude from successful clustering in polynomial time, even when it is information possible.
In this lecture, we will start by giving some intuitions on the minimal separation needed for successful clustering, regardless of computational complexity considerations. Then, we will discuss different approaches to exhibit computational barriers. We will focus on the « low-degree polynomial » paradigm, and briefly explain how it can be implemented to prove an Information-Computation gap in high-dimensional clustering. If time permits, we will also briefly explain how this gap collapses in an active setting.
