A. Atici and R. Servedio.

Preliminary version in

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.

Postscript or pdf (full version of conference paper)