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