<p>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 &gt; 0$.</p>

<hr>

<p>[1] <a href="https://arxiv.org/pdf/1201.1214.pdf" rel="nofollow noreferrer">Feldman, Vitaly, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao. "Statistical algorithms and a lower bound for detecting planted cliques." In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 655-664. ACM, 2013.</a></p>

CC BY-SA 3.0
2017-12-10T00:10:46.490Z
2017-12-10T00:10:46.490Z
Juho
<p>To answer the first part of your question, a conjecture in <a href="http://www.mathunion.org/ICM/ICM1983.2/Main/icm1983.2.1601.1610.ocr.pdf" rel="nofollow noreferrer">Karp'76</a> 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. </p>

CC BY-SA 3.0
2017-12-05T05:51:24.433Z
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.
CC BY-SA 3.0
2017-12-05T15:16:57.793Z
@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
CC BY-SA 3.0
2017-12-05T15:18:58.293Z
@ClementC. Thank you for helping clarify my intent. Much appreciated :).
mm8511
CC BY-SA 3.0
2017-12-05T05:44:48.250Z
2017-12-05T05:44:48.250Z
Ainesh Bakshi
<p>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.</p>

<p>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. </p>

<cc.complexity-theory><reference-request><time-complexity><clique><random-graphs>
Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$
mm8511
# Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$

(Asked by: username_0 on 2017-12-02)

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.

**Tags:** cc.complexity-theory, reference-request, time-complexity, clique, random-graphs

---

## 2 answers

### Answer by username_1 on 2017-12-10. Score: 3 | Accepted answer

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$.

---

[1] [Feldman, Vitaly, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao. "Statistical algorithms and a lower bound for detecting planted cliques." In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 655-664. ACM, 2013.](https://arxiv.org/pdf/1201.1214.pdf)


---

### Answer by username_2 on 2017-12-05. Score: 3

To answer the first part of your question, a conjecture in [Karp'76](http://www.mathunion.org/ICM/ICM1983.2/Main/icm1983.2.1601.1610.ocr.pdf) 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.

> **Comments:**
> **username_3**: 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.  
> **username_0**: @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})$.  
> **username_0**: @ClementC. Thank you for helping clarify my intent. Much appreciated :).  

---

