Learning Partitions using Rank Queries

Deeparnab Chakrabarty, Hang Liao

We consider the problem of learning an unknown partition of an $n$ element universe using rank queries. Such queries take as input a subset of the universe and return the number of…