文章基本信息

标题：A new approach to the planted clique problem
本地全文：下载
作者：Alan Frieze ; Ravi Kannan
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2008
卷号：2
页码：187-198
DOI：10.4230/LIPIcs.FSTTCS.2008.1752
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Planted Clique; Tensor; Random Graph