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

arXiv: https://arxiv.org/abs/2608.02176 · HTML: https://mlsanity.com/paper/2608.02176/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 29 references that are in the map.
- First posted on arXiv 3 Aug 2026.

## Builds on (most cited first, 16 of 16)

- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [Query Complexity of Clustering with Side Information](https://mlsanity.com/paper/1706.07719/) (2017)
- [Exact Recovery of Mangled Clusters with Same-Cluster Queries](https://mlsanity.com/paper/2006.04675/) (2020)
- [Same-Cluster Querying for Overlapping Clusters](https://mlsanity.com/paper/1910.12490/) (2019)
- [Leveraging Transitive Relations for Crowdsourced Joins](https://mlsanity.com/paper/1408.6916/) (2014)
- [A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution](https://mlsanity.com/paper/1702.01208/) (2017)
- [On Learning Graphs with Edge-Detecting Queries](https://mlsanity.com/paper/1803.10639/) (2018)
- [Clustering with Queries under Semi-Random Noise](https://mlsanity.com/paper/2206.04583/) (2022)
- [Tight query complexity bounds for learning graph partitions](https://mlsanity.com/paper/2112.07897/) (2021)
- [Learning Low Degree Hypergraphs](https://mlsanity.com/paper/2202.09989/) (2022)
- [Clustering with Non-adaptive Subset Queries](https://mlsanity.com/paper/2409.10908/) (2024)
- [Learning Partitions using Rank Queries](https://mlsanity.com/paper/2409.13092/) (2024)
- [Non-adaptive Learning of Random Hypergraphs with Queries](https://mlsanity.com/paper/2501.12771/) (2025)
- [Learning Partitions with Optimal Query and Round Complexities](https://mlsanity.com/paper/2505.05009/) (2025)
- [Query Complexity of Hypergraph Connectivity and Learnability using CUT Oracles](https://mlsanity.com/paper/2607.01216/) (2026)

## Abstract (arXiv)

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.