A new approach to the planted clique problem

Full textClick to download.
CitationIn proceedings of the 2008 Symposium on Foundations of Software Technology and Theoretical Computer Science, Bangalore, India
AuthorsAlan Frieze
Ravi Kannan


We study the problem of finding a large planted clique in the random graph $G_{n,1/2}$. We reduce the problem to that of maximising a three dimensional tensor over the unit ball in $n$ dimensions. This latter problem has not been well studied and so we hope that this reduction will eventually lead to an improved solution to the planted clique problem.

Back to publications
Back to previous page