Small Clique Detection and Approximate Nash Equilibria

Recently, Hazan and Krauthgamer showed [12] that if, for a fixed small epsilon, an epsilon-best epsilon-approximate Nash equilibrium can be found in polynomial time in two-player games, then it is also possible to find a planted clique in G(n, 1/2) of size C log n, where C is a large fixed constant independent of epsilon. In this paper, we extend their result to show that if an epsilon-best epsilon-approximate equilibrium can be efficiently found for arbitrarily small epsilon > 0, then one can detect the presence of a planted clique of size (2 + delta) log n in G(n, 1/2) in polynomial time for arbitrarily small delta > 0. Our result is optimal in the sense that graphs in G(n, 1/2) have cliques of size (2 - o(1)) log n with high probability.