论文标题
种植集团恢复的空间复杂性与检测相同吗？
Is the space complexity of planted clique recovery the same as that of detection?
论文作者
论文摘要
我们研究了种植的集团问题，其中将大小k的集团种植在erdős-rényi图G（n，1/2）中，并且一个人有兴趣检测或恢复该种植的集团。这个问题很有趣，因为人们普遍认为在集团大小k = sqrt {n}处显示统计计算差距，并且已经成为典型的问题，因为差距可以提出其他统计问题的平均硬度硬度的差距。与其他类似性质的问题不同，它还显示了检测和恢复变体之间的紧密计算连接。但是，对种植集团问题的计算复杂性的广泛研究主要集中在其时间复杂性上。在这项工作中，我们问 - 当我们使用“空间效率”作为计算效率的概念时，使种植集团成为有趣的问题的统计计算现象也存在吗？ 相对容易表明，对此问题的积极答案取决于O（log n）空间算法的存在，该算法可以恢复大小K = Omega（SQRT {N}）的种植库。我们的主要结果非常接近设计这种算法。我们表明，对于K = Omega（SQRT {N}），可以在O（（（log*{n} -log*{k/sqrt {n}}）log n）log n）位置中解决恢复问题。 1。如果k = omega（sqrt {n} log^{（l）} n）对于任何常数整数l> 0，则空间用法为o（log n）位。 2.如果k = theta（sqrt {n}），则空间用法为o（log*{n} log n）位。 我们的结果表明，确实存在一个O（log n）空间算法，以恢复大小k = omega（sqrt {n}）的集团，因为我们非常接近实现此类参数。这提供了证据，表明（构想）对种植集团的时间复杂性（猜想）的统计计算现象（构想）也具有空间复杂性。
We study the planted clique problem in which a clique of size k is planted in an Erdős-Rényi graph G(n, 1/2), and one is interested in either detecting or recovering this planted clique. This problem is interesting because it is widely believed to show a statistical-computational gap at clique size k=sqrt{n}, and has emerged as the prototypical problem with such a gap from which average-case hardness of other statistical problems can be deduced. It also displays a tight computational connection between the detection and recovery variants, unlike other problems of a similar nature. This wide investigation into the computational complexity of the planted clique problem has, however, mostly focused on its time complexity. In this work, we ask- Do the statistical-computational phenomena that make the planted clique an interesting problem also hold when we use `space efficiency' as our notion of computational efficiency? It is relatively easy to show that a positive answer to this question depends on the existence of a O(log n) space algorithm that can recover planted cliques of size k = Omega(sqrt{n}). Our main result comes very close to designing such an algorithm. We show that for k=Omega(sqrt{n}), the recovery problem can be solved in O((log*{n}-log*{k/sqrt{n}}) log n) bits of space. 1. If k = omega(sqrt{n}log^{(l)}n) for any constant integer l > 0, the space usage is O(log n) bits. 2.If k = Theta(sqrt{n}), the space usage is O(log*{n} log n) bits. Our result suggests that there does exist an O(log n) space algorithm to recover cliques of size k = Omega(sqrt{n}), since we come very close to achieving such parameters. This provides evidence that the statistical-computational phenomena that (conjecturally) hold for planted clique time complexity also (conjecturally) hold for space complexity.
