10.4230/LIPICS.FSTTCS.2008.1752
Frieze, Alan
Alan
Frieze
Kannan, Ravi
Ravi
Kannan
A new approach to the planted clique problem
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Planted Clique
Tensor
Random Graph
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
2008
2008-12-05
2008-12-05
2008-12-05
en
urn:nbn:de:0030-drops-17521
10.4230/LIPIcs.FSTTCS.2008
978-3-939897-08-8
1868-8969
10.4230/LIPIcs.FSTTCS.2008
LIPIcs, Volume 2, FSTTCS 2008
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
2013
2
5
187
198
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
2
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
435443 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 187-198