| Full text | Click to download. |
| Citation | In proceedings of the 2008 Symposium on Foundations of Software Technology and Theoretical Computer Science, Bangalore, India
|
| Authors | Alan 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.