Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$
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.