Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

I will discuss models for random graphs that contain a hidden structure such as denser "communities" within a sparser ambient graph. The goal is to determine the best possible (in a rigorous sense) methods for extracting the hidden structure. These tasks often have inherent tradeoffs between statistical and computational efficiency, which cannot be understood using the classical theory from statistics or computer science. I will give an overview of my work that uses low-degree polynomials to find optimal algorithms and identify fundamental barriers.