The 1W-MINDS Seminar was founded in the early days of the COVID-19 pandemic to mitigate the impossibility of travel. We have chosen to continue the seminar since to help form the basis of an inclusive community interested in mathematical data science, computational harmonic analysis, and related applications by providing free access to high quality talks without the need to travel. In the spirit of environmental and social sustainability, we welcome you to participate in both the seminar, and our slack channel community! Zoom talks are held on Thursdays at 2:30 pm New York time. To find and join the 1W-MINDS slack channel, please click here.
Current Organizers (September 2026 - May 2027): March Boedihardjo (Michigan State University), Hung-Hsu Chou (University of Pittsburgh), Longxiu Huang (Michigan State University), Mark Iwen (Principal Organizer, Michigan State University), and Kunlun Qi (Michigan State University).
Most previous talks are on the seminar YouTube channel. You can catch up there, or even subscribe if you like.
To sign up to receive email announcements about upcoming talks, click here.
To join MINDS slack channel, click here.
Passcode: the smallest prime > 100
We study the theoretical limits of local algorithms based on the modularity score to recover planted communities in random graphs. The modularity score $q_{\mathcal{A}}(G)$ gives a measure of how well the vertex partition $\mathcal{A}$ divides the graph $G$ into `communities'; and is central to the most popular algorithms used to cluster real network data. We consider recovery in the Stochastic Block Model (SBM) where the graph $G$ has a planted $k$-block partition where vertices within the same block connect with probability $p$ while vertices in different blocks connect with probability $q$, independently across pairs of vertices. The overlap gap property (OGP) is a statement about the geometry of near-optimal solutions. We establish that modularity exhibits OGP on the SBM. This rules out recovery in the SBM by a class of local algorithms based on the modularity score and shows slow mixing time for a related Markov Chain. Theoretically this is one of the few instances where OGP has been established on a `planted' rather than `null' model. As part of our proof we extend a result by Bickel and Chen [PNAS 2009]; who established that with high probability, a modularity optimal partition of SBM is few local moves away from the planted partition; we extend this to non-optimal partitions whose score is sufficiently close to the optimum score.
Joint work with Shankar Bhamidi, David Gamarnik, Remco van der Hofstad, Nelly Litvak, Pawel Pralat and Yasmin Tousinejad. ICALP 2026 DOI :https://doi.org/10.4230/LIPIcs.ICALP.2026.28