参照要求:$ G(n、1/2)$の$(1+ ε) log n $ sizeクリークを見つけるための複雑さの結果

私は$ G(n、1/2)$の$(1+ ε) log n
$サイズのクリークを見つけるための最もよく知られた時間の複雑さに関する結果を見つけようとしています。より一般的な結果は素晴らしいでしょう。つまり、もし$
C_p $が$ G_(n、p)$のサイズ$ C_p log n
$のクリークを明らかに見つけるような定数であるならば、サイズ$(C_p + epsilon) log n
$のクリークはさらに良いでしょう。

特に、$ O(n ^ { epsilon ^ 2 log n})を使って$ G(n、p)$内の$(C_p +
epsilon) log n $クリークを見つける方法を知っているかどうかに興味があります。 )$ timeと$ O(n ^ {
epsilon ^ 2 log n})$スペース。これらの時間と空間の制約下で高い確率で$(C_p + ε) log n
$の頂点クリークを発見するランダム化アルゴリズムは、公開可能な結果を​​構成するでしょうか?関連する文献への指針は非常に高く評価されるだろう。

ベストアンサー

Feldman et al. [1] give several references to methods for e.g.,
finding cliques of size $k = Omega(sqrt{n})$, including spectral
methods, SDPs, combinatorial methods, nuclear norm minimization,
and belief propagation. They also say the quasipolynomial-time
algorithm is the fastest one known for planted $k$-clique detection
for any $k=O(n^{1/2−delta})$, where $delta > 0$.


[1] Feldman, Vitaly, Elena Grigorescu, Lev
Reyzin, Santosh Vempala, and Ying Xiao. “Statistical algorithms and
a lower bound for detecting planted cliques.” In Proceedings of the
Forty-Fifth Annual ACM Symposium on Theory of Computing, pp.
655-664. ACM, 2013.

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です