Loading...
Please wait, while we are loading the content...
Similar Documents
An integrality gap for the planted clique problem
| Content Provider | Semantic Scholar |
|---|---|
| Author | Barak, Boaz Steurer, David Kothari, Pravesh Potechin, Aaron |
| Abstract | The Planted Clique problem (sometimes referred to as the hidden clique problem) is a central question in average-case complexity where one is interested in the computational complexity of solving typical (as against worst-case) instances. The problem is rooted in the 1976 work of Karp (Karp [1976]) that asked to find a maximum clique (i.e., set of vertices that are all neighbors of one another) in a Erdös-Rényi random graph G(n, 2 ) (where every edge is included independently in the graph with probability 2 independently). 1 Jerrum (Jerrum [1992]) and Kucera (Kucera [1995]) defined Planted Clique as a relaxation of this problem: for some ω ∈ {1, . . . , n}, find an ω clique added to an Erdös-Rényi random graph G ∼ G(n, 2 ). That is, we choose G as a random graph from G(n, 2 ), choose S to be a random ω-sized subset of [n] and then add to G all the edges between pairs of vertices in S. As the exercise below shows, the problem can be solved by brute force search in quasi-polynomial time as long as ω log (n). |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.sumofsquares.org/public/lec-lowerbound-plantedclique.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
