# Question about the lower bound for $k \times k$-clique (under ETH) shown in “Slightly Superexponential Parameterized Problems”

I am reading the paper Slightly Superexponential Parameterized Problems at the moment and have two questions about it:

First question: The paper gives a proof of the following statement

Theorem 2.1: Assuming ETH, there is no $$2^{o(klogk)}$$ time algorithm for $$k \times k$$-Clique.

They prove this statement by sophisticated reduction from $$3$$-coloring. They then state that this construction runs in time polynomial in $$k$$. They state:

The graph $$G$$ has $$k^2$$ vertices and the time required to construct G is polynomial in $$k$$. [...] Therefore, the total running time is $$2^{o(k \log(k)} \cdot k^{O(1)}$$

Why is this not $$2^{o(k \log(k)}) + k^{O(1)}$$ instead? As far as I can see, we have only have to construct the graph once, and then we can run the presumed $$2^{o(k \log(k)}$$ algorithm.

Second question: From this theorem, it follows that $$k \times k$$-Clique can not have a $$k^{o(k)}$$ algorithm under the Exponential Time Hypothesis. This follows from the abstract, which states that $$k^{O(k)} = 2^{O(k \log(k))}$$. What is a good way to proof this statement?

• Regarding your first question, it might be a typo. It doesn't make a huge difference anyway. – Yuval Filmus Aug 25 '19 at 21:12
• Regarding the second question, try using $k^k = 2^{k\log k}$ (assuming the base of the logarithm is 2, which doesn't matter for something like $2^{o(k\log k)}$ or even $2^{O(k\log k)}$). – Yuval Filmus Aug 25 '19 at 21:12