Optimal Algorithms for Learning Partitions with Faulty Oracles

We consider a clustering problem where a learner seeks to partition a finite set by querying a faulty oracle. This models applications where learners crowdsource information from non-expert human workers or conduct noisy experiments to determine group structure. The learner aims to exactly recover a partition by submitting queries of the form are u and v in the same group?'' Moreover, because the learner only has access to faulty sources of information, they require an error-tolerant algorithm for this task: i.e. they must fully recover the correct partition, even if up to \ell answers are incorrect, for some error-tolerance parameter \ell . We study the question: for any given error-tolerance \ell, what is the minimum number of queries needed to learn a finite set partition of n elements into k groups?