Revisiting Jerrum's Metropolis Process for the Planted Clique Problem

Watch a Harvard CMSA lecture where MIT's Ilias Zadik explores the limitations of Jerrum's Metropolis process in solving the planted clique problem. Delve into the mathematical analysis showing how this process fails to recover planted cliques of size o(n) under worst-case initialization, extending well beyond the previously established sqrt(n) threshold. Learn about the resolution of Jerrum's 1992 open question regarding natural initialization failure across multiple temperature values. Follow the detailed proof ideas and theoretical framework, from the basics of cliques in random graphs to advanced concepts in the planted clique model, concluding with future research directions in this fundamental algorithmic problem.