Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds

We study the round complexity of learning a hidden partition P of an n-element universe using PAIR queries: PAIR(x,y) tells us whether x and y belong to the same part of the partition or not. While it is easy to learn using n|P| queries using a basic algorithm and this query complexity is optimal, this basic algorithm is highly sequential. Black, Mazumdar, and Saha [COLT 2025] recently gave tight deterministic round/query tradeoffs when the number of parts of P is known. In particular they prove Theta(loglog n) rounds are sufficient and necessary to limit the number of queries to n|P|. They leave proving a randomized lower bound as an open direction. We show that randomization dramatically changes the picture. When the number of parts k = |P| is known, we give a simple 3-round randomized algorithm using O(nklog n) queries with high probability, and prove that 2 rounds require Omega(n4/3k2/3) queries -- the same as deterministic algorithms. We also study a more general setting where the number of parts is unknown. In this case, we give a 4-round randomized algorithm using O(n|mathcal P|log2 n) queries with high probability, and prove that 3-rounds cannot achieve near-optimal query complexity. Furthermore, we show an even bigger separation in this regime between randomized and deterministic algorithms: for the latter, Theta(log n/loglog n) rounds are necessary and sufficient to obtain near-optimal query complexity.