Clustering with an oracle
Arya Mazumdar, Barna Saha · 2016
Suppose, we are given V = {1, 2, …, n} ≡ [n], a set of n points, that can be clustered into k parts Vi, i = 1, …, k; Vi∩ Vj= ∅, ∀i ≠ j; the subsets Vi⊂ [n] and k are unknown to us. There is an oracle that can answer any pair-wise queries V × V → {±1}, where a query answer of +1 for (u, v) ∈ V ×V indicates u and v belong to the same cluster, and −1 indicates they do not. How many such queries are necessary and/or sufficient to find the clusters exactly?