Georgia Institute of Technology College of Sciences

For general graphs, approximating the maximum clique is a notoriously hard problem even to approximate to a factor of nearly n, the number of vertices. Does the situation get better with random graphs? A random graph on n vertices where each edge is chosen with probability 1/2 has a clique of size nearly 2\log n with high probability. However, it is not know how to find one of size 1.01\log n in polynomial time. Does the problem become easier if a larger clique were planted in a random graph? The current best algorithm can find a planted clique of size roughly n^{1/2}. Given that any planted clique of size greater than 2\log n is unique with high probability, there is a large gap here. In an intriguing paper, Frieze and Kannan introduced a tensor-based method that could reduce the size of the planted clique to as small as roughly n^{1/3}. Their method relies on finding the spectral norm of a 3-dimensional tensor, a problem whose complexity is open. Moreover, their combinatorial proof does not seem to extend beyond this threshold. We show how to recover the Frieze-Kannan result using a purely probabilistic argument that generalizes naturally to r-dimensional tensors and allows us recover cliques of size as small as poly(r).n^{1/r} provided we can find the spectral norm of r-dimensional tensors. We highlight the algorithmic question that remains open. This is joint work with Charlie Brubaker.