Improved Hardness of Approximating k-Clique under ETH

Bingkai Lin, Xuandi Ren, Yican Sun +1

In this paper, we prove that assuming the exponential time hypothesis (ETH), there is no $f(k)\cdot n^{k^{o(1/\log \log k)}}$-time algorithm that can decide whether an $n$-vertex gr…