| Planted clique problem is a central problem in average-case complexity.In planted clique problem,we are given a random graph with a planted l(n)-sized clique and are asked to find out this clique.By "planting" we means uniformly at random choosing k(n)vertices and then adding all edges between such vertices into the graph.We extend the planted clique model g(n,1/2,k(n))into g(n,p(n),k(n)),and give t(n)=o(log n)condition for small edge probability.In this extended model,we prove generalization of classical results,obtaining universal quasi-polynomial-time algorithms for planted cliques.With small edge probability,we prove that there exists polynomial-time randomized algorithm to find planted clique of size c·(?)=o(?)with high probability.We study the AC0[q]-circuit lower bounds for planted clique,find-ing incompatibility of Razborov-Smolensky method and planted clique problem,and giving some possible directions for further research. |
