Is Planted Coloring Easier than Planted Clique? - A Study of Statistical-Computational Gaps

Watch a 55-minute Harvard CMSA lecture exploring the computational complexity differences between planted coloring and planted clique problems in graph theory. Delve into the analysis of three key tasks - detection, recovery, and refutation - within these models, with UC Davis speaker Alex Wein demonstrating how these tasks, while equally challenging for planted clique, show varying levels of difficulty in planted coloring scenarios. Learn how adding multiple planted cliques through graph complementation makes detection more manageable while maintaining recovery complexity. Examine computational hardness proofs based on low-degree polynomial computation models, and understand the mathematical framework behind partial coloring, standard approaches, and refutation definitions. Follow along as the lecture progresses from fundamental concepts through various problem types to alternative methodological approaches, culminating in a comprehensive comparison of these significant graph theory challenges.