Finding the Rare Cube

Abstract

In this paper we investigate the problem of active learning the partition of the n -dimensional hypercube into m  cubes, where the i -th cube has color  i . The model we are using is exact learning via color evaluation queries , without equivalence queries, as proposed by the work of Fine and Mansour. We give a randomized algorithm solving this problem in O ( m log n ) expected number of queries, which is tight, while its expected running time is O ( m ^2 n log n ). Furthermore, we generalize the problem to allow partitions of the cube into m monochromatic parts, where each part is the union of p cubes. We give two randomized algorithms for the generalized problem. The first uses O ( m p ^2 2^ p log n ) expected number of queries , which is almost tight with the lower bound. However, its naïve implementation requires an exponential running time in  n . The second, more practical, algorithm achieves a better running time complexity of $\tilde{O}(m^2 n^2 2^{2^p})$ . However, it may fail to learn the correct partition with an arbitrarily small probability and it requires slightly more expected number of queries: $\tilde{O}(mn 4^p)$ , where the $\tilde{O}$ represents a poly logarithmic factor in m , n ,2^ p .