# Learning Partitions with Optimal Query and Round Complexities

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 46 references that are in the map.
- First posted on arXiv 8 May 2025.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Query Complexity of Clustering with Side Information](https://mlsanity.com/paper/1706.07719/) (2017)
- [Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost](https://mlsanity.com/paper/1908.04976/) (2019)
- [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)
- [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)
- [Semisupervised Clustering by Queries and Locally Encodable Source Coding](https://mlsanity.com/paper/1904.00507/) (2019)
- [Tight query complexity bounds for learning graph partitions](https://mlsanity.com/paper/2112.07897/) (2021)
- [Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oracle](https://mlsanity.com/paper/2202.08522/) (2022)
- [Cut query algorithms with star contraction](https://mlsanity.com/paper/2201.05674/) (2022)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [Computing exact minimum cuts without knowing the graph](https://mlsanity.com/paper/1711.03165/) (2017)
- [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)
- [On the query complexity of connectivity with global queries](https://mlsanity.com/paper/2109.02115/) (2021)

## Built on by (most cited first, 2 of 2)

- [Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds](https://mlsanity.com/paper/2608.02176/) (2026)
- [Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Fewer Measurements](https://mlsanity.com/paper/2609.32176/) (2026)

## Abstract (arXiv)

We consider the basic problem of learning an unknown partition of n elements into at most k sets using simple queries that reveal information about a small subset of elements. Our starting point is the well-studied pairwise same-set queries which ask if a pair of elements belong to the same class. It is known that non-adaptive algorithms require Theta(n2) queries, while adaptive algorithms require Theta(nk) queries, and the best known algorithm uses k-1 rounds. This problem has been studied extensively over the last two decades in multiple communities due to its fundamental nature and relevance to clustering, active learning, and crowd sourcing. In many applications, it is of high interest to reduce adaptivity while minimizing query complexity. We give a complete characterization of the deterministic query complexity of this problem as a function of the number of rounds, r, interpolating between the non-adaptive and adaptive settings: for any constant r, the query complexity is Theta(n^1+frac12r-1k^1-frac12r-1). Our algorithm only needs O(log log n) rounds to attain the optimal O(nk) query complexity. Next, we consider two generalizations of pairwise queries to subsets S of size at most s: (1) weak subset queries which return the number of classes intersected by S, and (2) strong subset queries which return the entire partition restricted on S. Once again in crowd sourcing applications, queries on large sets may be prohibitive. For non-adaptive algorithms, we show Omega(n2/s2) strong queries are needed. Perhaps surprisingly, we show that there is a non-adaptive algorithm using weak queries that matches this bound up to log-factors for all s ≤ √n. More generally, we obtain nearly matching upper and lower bounds for algorithms using subset queries in terms of both the number of rounds, r, and the query size bound, s.