Query Complexity of Learning Axis-Aligned Partitions

This work establishes the query complexity of learning high-dimensional boxes in the exact query learning setting. Let $X \subset \mathbb{R}^d$ be a set of $n$ points, labeled by a collection of $k$ boxes: the label of each point in $X$ is determined by the unique box containing it. A learner aims t