21 citations · 61 across the 21 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.CC2015
SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin
The problem of finding large cliques in random graphs and its "planted" variant, where one wants to recover a clique of size added to an \Erdos-\Renyi graph $G \si…
cs.CC2015★ 13 cited
Sum-of-squares lower bounds for planted clique
Raghu Meka, Aaron Potechin, Avi Wigderson
Finding cliques in random graphs and the closely related "planted" clique variant, where a clique of size k is planted in a random G(n, 1/2) graph, have been the focus of substanti…