Distributed Discovery of Large Near-Cliques

Zvika Brakerski, Boaz Patt-Shamir

Given an undirected graph and $0\le \epsilon \le 1$, a set of nodes is called $\epsilon$-near clique if all but an $\epsilon$ fraction of the pairs of nodes in the set have a link between them. In this pa…