What are the best known upper bounds and lower bounds for computing O(log n)-Clique?

Question

Input: a graph with n nodes, Output: A clique of size $O(\log n)$, Providing links to references would be great

Answer 1

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.

Answer 2

An earlier observation in the same vein as Williams' is given in "Limited vs. Polynomial Nondeterminism" by Feige and Kilian in The Chicago Journal of Theoretical Computer Science (1997)

Answer 3

A (not unconditional) lower bound comes from the clique problem being complete for the parameterized complexity class W1. That is, we do not expect to be able to find a clique of size $k$ in $f(k)n^c$. So there is good reason to believe that the trivial upper bound may not be significantly improved.

Answer 4

As I understand it this problem is interesting even for random graphs (in the Erdős–Rényi model in which all graphs are equally likely): we know that the maximum clique size is $(2+o(1))\log_2 n$, but the biggest cliques we can find in polynomial time (e.g. by finding any maximal clique) have size only $(1+o(1))\log_2 n$. See e.g. the introduction of Alon, Krivelevich, and Sudakov, "Finding a large hidden clique in a random graph", SODA 1998, where they credit these observations to a 1976 paper of Karp and conjecture that no polynomial algorithm can do better than $(1+o(1))\log_2 n$.