# Search vs Decision vs Certification for Planted Problems

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.

# Beyond Worst-Case Analysis: Lecture 7

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 ${G_{n,\frac{1}{2}}}$. At the end of this class, we wrapped up this topic and started the topic of ${k}$-SAT.

1. Planted Clique

To start with, we describe a distribution of graphs with a planted clique. Suppose that we sample ${G}$ from ${G_{n,\frac{1}{2}}}$ and we want to modify ${G}$ s.t. it has a size ${k}$ clique, i.e., we have a clique ${S \subseteq V}$ with ${\left|S\right|=k}$. The following code describes a sampler for the distribution.

• ${G \leftarrow G_{n,\frac{1}{2}}}$
• Pick a subset of vertices ${S}$ from ${V}$ s.t. ${|S|=k}$
• Independently for each pair ${\{u,v\}}$, make ${\{u,v\}}$ an edge with probability
• ${1}$ if ${u,v \in S}$
• ${\frac 12}$ otherwise

Note: We are only interested in the case ${k \geq 2\log n}$, which is the case in which the planted clique is, with high probability, larger than any pre-existing clique