Edited 5/7/2018. Thanks to Sam Hopkins for several corrections and suggestions.
I am revising my notes from the course on “better-than-worst-case” analysis of algorithms. With the benefit of hindsight, in this post (and continuing in future posts) I would like to review again how one applies spectral methods and semidefinite programming to problems that involve a “planted” solution, and what is the role of concentration results for random matrices in the analysis of such algorithms.
Scribed by Jeff Xu
In which we discussed planted clique distribution, specifically, we talked about how to find a planted clique in a random graph. We heavily relied upon our material back in lecture 2 and lecture 3 in which we covered the upper bound certificate for max clique in . At the end of this class, we wrapped up this topic and started the topic of -SAT.
1. Planted Clique
To start with, we describe a distribution of graphs with a planted clique. Suppose that we sample from and we want to modify s.t. it has a size clique, i.e., we have a clique with . The following code describes a sampler for the distribution.
- Pick a subset of vertices from s.t.
- Independently for each pair , make an edge with probability
Note: We are only interested in the case , which is the case in which the planted clique is, with high probability, larger than any pre-existing clique