Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds
2026-08-03 • Data Structures and Algorithms
Data Structures and AlgorithmsMachine Learning
AI summaryⓘ
The authors study how many rounds of asking paired questions are needed to learn how a set is divided into groups. They focus on using queries that check if two elements are in the same group and look at both deterministic and randomized methods. Their results show that using randomness can significantly reduce the number of rounds needed compared to deterministic methods, especially when the number of groups is unknown. They provide new algorithms and prove limits on how efficient these algorithms can be depending on the number of rounds allowed.
hidden partitionpair queriesround complexityrandomized algorithmsdeterministic algorithmsquery complexityhidden clustersalgorithmic lower boundsquery rounds
Authors
Deeparnab Chakrabarty, Aditi Dudeja, David Saulpic
Abstract
We study the round complexity of learning a hidden partition $\mathcal{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|\mathcal{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 $\mathcal{P}$ is known. In particular they prove $Θ(\log\log n)$ rounds are sufficient and necessary to limit the number of queries to $n|\mathcal{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 = |\mathcal{P}|$ is known, we give a simple 3-round randomized algorithm using $O(nk\log n)$ queries with high probability, and prove that 2 rounds require $Ω(n^{4/3}k^{2/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|\log^2 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, $Θ(\log n/\log\log n)$ rounds are necessary and sufficient to obtain near-optimal query complexity.