Learning Unions of \omega(1)-Dimensional Rectangles.
A. Atici and R. Servedio.
Theoretical Computer Science, 405(3), 2008, pp. 209--222.
Preliminary version in Seventeenth International Conference on Algorithmic Learning Theory (ALT), 2006, pp. 32-47.

Abstract:

We consider the problem of learning unions of rectangles over the domain $\{0,1,\dots,b-1\}^n$, in the uniform distribution membership query learning setting, where both $b$ and $n$ are large''. We obtain poly$(n, \log b)$-time algorithms for various subclasses of unions of rectangles over this domain. Our main algorithmic tool is an extension of Jackson's boosting- and Fourier-based Harmonic Sieve algorithm to the domain $\{0,1,\dots,b-1\}$, building on work of Akavia {\em et al.}. Other ingredients used to obtain the results stated above are techniques from exact learning and ideas from recent work on learning augmented $AC^0$ circuits and on representing Boolean functions as thresholds of parities.