Exact Recovery of Mangled Clusters with Same-Cluster Queries (supplementary material)

We recall Y ao's minimax principle for Monte Carlo algorithms. Then (see [4], Proposition 2.6): max Lemma 8 (20) In the rest of the proof we prove the four lemmata. Let z be the point w.r.t. which the margin of C holds. The proof of the theorem is complete. In this section we show how to compute the separator of Theorem 3. In fact, computing the separator (see Section 5).