What are the best known upper bounds and lower bounds for computing O(log n)-Clique? Input: a graph with n nodes,
Output: A clique of size $O(\log n)$,
Providing links to references would be great
The best known upper bound is essentially $n^{O(\log n)}$. You can improve a little on the constant factor in the big-O using fast matrix multiplication, but that's about it. There are a lot of algorithmic references on the $k$-clique problem which describe this reduction, it originates from papers of Itai and Rodeh and Nesetril and Poljak. (Apologies to Czech readers, I am ignorant of the proper diacritical marks.) See http://en.wikipedia.org/wiki/Clique_problem

If you could solve $\log n$-clique in $n^{\varepsilon \log n}$ for every $\varepsilon > 0$, then you could also solve 3SAT in subexponential time. This can be seen as a "lower bound" to further progress. One way to prove this is to first show that if $\log n$-clique in $n^{\varepsilon \log n}$ for every $\varepsilon > 0$, then MaxCut on $n$ nodes is in $2^{\varepsilon n}$ time for every $\varepsilon > 0$. This follows directly from a theorem in my ICALP'04 paper that relates the time complexity of MaxCut to the time complexity of $k$-clique. From there, one can appeal to standard reductions to reduce 3SAT to MaxCut, showing that subexponential MaxCut implies subexponential 3SAT.

In terms of unconditional lower bounds, nothing nontrivial is known, to my knowledge. We don't even know how to show that $O(\log n)$-clique isn't solvable with an algorithm that runs in linear time and uses only logarithmic workspace.