  This paper initiates the study of active learning for exact recovery of
partitions exclusively through access to a same-cluster oracle in the presence
of bounded adversarial error. We first highlight a novel connection between
learning partitions and correlation clustering. Then we use this connection to
build a R\'enyi-Ulam style analytical framework for this problem, and prove
upper and lower bounds on its worst-case query complexity. Further, we bound
the expected performance of a relevant randomized algorithm. Finally, we study
the relationship between adaptivity and query complexity for this problem and
related variants.

Data Structures and Algorithms;Machine Learning;Machine Learning