Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares

Andreas Göbel, Janosch Ruff, Leon Schiller

We study efficient algorithms for recovering cliques in dense random intersection graphs (RIGs). In this model, $d=n^{\Omega (1)}$ cliques of size approximately $k$ are randomly plante…