Olga Medrano Martín del Campo

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…