# Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$

I am trying to find results on the best known time complexity for finding $(1+\epsilon) \log n$ sized cliques in $G(n,1/2)$. More general results would be great, i.e. if $C_p$ is the constant such that the obvious greedy algorithm finds a clique of size $C_p \log n$ in $G(n,p)$ almost surely, then any results on finding a clique of size $(C_p + \epsilon ) \log n$ would be even better.

In particular, I am interested in whether we know how to find a $(C_p +\epsilon)\log n$ clique in $G(n,p)$ using $O(n^{\epsilon^2\log n})$ time and $O(n^{\epsilon^2\log n})$ space. Would a randomized algorithm that finds a $(C_p +\epsilon)\log n$ vertex clique with high probability under these time and space constraints constitute a publishable result? Any pointers to relevant literature would be greatly appreciated.

Feldman et al. [1] give several references to methods for e.g., finding cliques of size $k = \Omega(\sqrt{n})$, including spectral methods, SDPs, combinatorial methods, nuclear norm minimization, and belief propagation. They also say the quasipolynomial-time algorithm is the fastest one known for planted $k$-clique detection for any $k=O(n^{1/2−\delta})$, where $\delta > 0$.
To answer the first part of your question, a conjecture in Karp'76 states that there is no efficient algorithm to find cliques of size $(1+ \epsilon)\log(n)$ for $G(n, 1/2)$. This conjecture is still open.
• But the OP is asking for algorithms even running in quasi-polynomial time ($n^{\varepsilon^2\log n}$), so the fact that the conjecture of Karp is still unresolved does not give tha much information about this specific question. – Clement C. Dec 5 '17 at 5:51
• @AineshBakshi I am familiar with this result, and I also know of some quasi-polynomial time results based off of repeatedly running the greedy algorithm for finding maximal cliques. The best result I found was based off of this and has expected running time $O(n^{ \frac{(1+\epsilon) \log n}{4}+O(1)})$. This was discovered a few decades ago, and I doubt it's still "state of the art." I am hard-pressed to find an algorithm with expected running time of even $O(n^{ \epsilon \log n})$ instead of $O(n^{ \epsilon^{2} \log n})$. – mm8511 Dec 5 '17 at 15:16