# Learning Partitions using Rank Queries

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Sep 2024.

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

- [Learning Partitions with Optimal Query and Round Complexities](https://mlsanity.com/paper/2505.05009/) (2025)
- [Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs](https://mlsanity.com/paper/2506.08405/) (2025)
- [Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds](https://mlsanity.com/paper/2608.02176/) (2026)

## Abstract (arXiv)

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 parts of the partition it intersects. We give a simple O(n)-query, efficient, deterministic algorithm for this problem. We also generalize to give an O(n + klog r)-rank query algorithm for a general partition matroid where k is the number of parts and r is the rank of the matroid.