Learning Partitions using Rank Queries
<|reference_start|>Learning Partitions using Rank Queries: 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 + k\log r)$-rank query algorithm for a general partition matroid where $k$ is the number of parts and $r$ is the rank of the matroid.<|reference_end|>
@article{chakrabarty2024learning,
    title={Learning Partitions using Rank Queries},
    author={Deeparnab Chakrabarty and Hang Liao},
    journal={arXiv preprint arXiv:2409.13092},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.13092},
    primaryClass={cs.DS}
}