Location: Gilman 132
When: November 2nd at 1:30 p.m.
Title: Revisiting the Metropolis Process for the Planted Clique Model Revisiting Process
Abstract: Jerrum in 1992 (co-)introduced the planted clique model by proving the (worst-case initialization) failure of the Metropolis process to recover any o(sqrt(n))-sized clique planted in the Erdos-Renyi graph G(n,1/2). This result is classically cited in the literature of the problem, as the “first evidence” the o(sqrt(n))-sized planted clique recovery task is “algorithmically hard”. In this work, we show that the Metropolis process actually fails to work (under worst-case initialization) for any o(n)-sized planted clique, that is the failure applies well beyond the sqrt(n) “conjectured algorithmic threshold”. Moreover we also prove, for a large number of temperature values, that the Metropolis process fails also under “natural initialization” resolving an open question by Jerrum in 1992.
This is joint work with Zongchen Chen and Elchanan Mossel.
Bio: Ilias Zadik is an Assistant Professor of Statistics and Data Science at Yale. He received his PhD from MIT in 2019, advised by David Gamarnik. Prior to Yale he held postdoctoral positions at MIT, mentored by Elchanan Mossel and Nike Sun, and at NYU. His interests span high dimensional statistics, probability theory and theoretical computer science, and some of his recent work focuses on the study of computational-statistical trade-offs and sharp threshold phenomena.
Zoom link: https://wse.zoom.us/j/94601022340