Clustering with Noisy Queries

In this paper, we provide a rigorous theoretical study of clustering with noisy queries. Given a set of n elements, our goal is to recover the true clustering by asking minimum number of pairwise queries to an oracle. Oracle can answer queries of the form "do elements u and v belong to the same cluster?"-the