Learning Partitions using Rank Queries

2024/09/19 by Chakrabarty, Deeparnab, Liao, Hang · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2409.13092

Abstract

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.

Cited by

• Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
• Learning Partitions with Optimal Query and Round Complexities
• Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds

Related

• Learning Partitions with Optimal Query and Round Complexities
• Faster Matroid Partition Algorithms
• Tight query complexity bounds for learning graph partitions
• On the Parallel Complexity of Finding a Matroid Basis
• Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle