3 papers
cs.DS2026
Learning Nearest-Neighbor Maps from Adaptive Queries
Hadley Black, Geelon So
We study the problem of learning nearest-neighbor maps from adaptive queries, which is equivalent to the following problem of reconstructing a hidden set via a nearest-neighbor…
cs.DS2025
Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
Hadley Black, Arya Mazumdar, Barna Saha +1
The graph reconstruction problem has been extensively studied under various query models. In this paper, we propose a new query model regarding the number of connected components,…
cs.DS2025
Learning Partitions with Optimal Query and Round Complexities
Hadley Black, Arya Mazumdar, Barna Saha
We consider the basic problem of learning an unknown partition of elements into at most sets using simple queries that reveal information about a small subset of elements.…