For the second part, we invoke Corollary 9.3 of . While their result is more general, in our context it specializes to the following: Theorem 3.2 ). Let A be a graph drawn from the semi-random model with a planted clique of size k. Then there is a polynomial time algorithm which, with probability 1 − exp(−Ω(k)), outputs setsŜ 1 , . . . ,Ŝ m with m ≤ 4n k , such that min m j=1 |S△Ŝ j | = O (n/k) 2 log(n).
Now for a large enough constant C, if k ≥ C ·n 2/3 log 1/3 (n) then the bound in Theorem 3.2 translates to |S△Ŝ j | ≤ k 8 . Then, any vertex i ∈ S will be connected to at least 7k 8 elements inŜ j , while with probability 1 − n exp(−Ω(k)), no vertex not in S will be connected to more than 3k 4 elements inŜ j . We can thus definẽ S j to be the set of vertices that are connected to at least 7k 8 elements inŜ j , and with high probability one of theS j will be the planted clique S.

### Language ###
English

### Assessment ###
The text mentions a specific threshold for parameter k in terms of n, which could be a natural question about algorithmic requirements.

### Query ###
What is the minimum size requirement for k in relation to n for the algorithm to work?
What is the minimum size requirement for k in relation to n for the algorithm to work?