Clique is hard to approximate within \(n^{1-\epsilon}\) (Q1588908)

The author of the paper studies the possible performance of a polynomial-time approximation algorithm for the optimization version of the CLIQUE problem, traditionally denoted Max-Clique, which given a graph \(G\) and an integer \(k\) tries to identify whether there are \(k\) nodes all of which are connected in graph \(G\). The author strengthens the results of Bellare, Goldreich and Sudan who proved that, for any \(\varepsilon> 0\), Max-Clique cannot be efficiently approximated within \(n^{1/3-\varepsilon}\), to prove that, for any \(\varepsilon> 0\), Max-Clique cannot be efficiently approximated within \(n^{1-\varepsilon}\).