CS264: Beyond Worst-Case Analysis Lecture #10: Planted and Semi-Random Graph Models
Tim Roughgarden · 2014
Lectures #6–8 proposed several different “stability conditions ” on problem instances, of var-ious NP-hard clustering and graph partitioning problems, under which the exact recovery of the optimal solution is possible in polynomial time. These stability conditions were rea-sonably natural, in that there was a plausible narrative about why “real-world ” instances might tend to satisfy them (at least approximately).1 Last lecture (Lecture #9), we gave a sufficient condition for the computationally efficient recovery of sparse solutions to underdetermined linear systems. The condition was techni-cal — that the kernel of the constraint matrix A is an almost Euclidean subspace — but was justified by the (omitted) proof that random matrices satisfy the condition with high probability (for many different distributions on matrices). Today we continue our ongoing study of the polynomial-time exact recovery of “planted” or “ground truth ” solutions. We’ll study randomized models (i.e., input distributions) that share some spirit with the stability conditions of Lectures #6–8, in that the optimal solution tends to “stick out. ” The goals are to design and analyze polynomial-time algorithms that recover the optimal solution with high probability (over the input distribution), and to understand how far the optimal solution to an NP-hard problem has to stick out before exact recovery is possible in polynomial time. ∗ c©2014, Tim Roughgarden.