Learning unions of ω(1)-dimensional rectangles

We consider the problem of learning unions of rectangles over the domain [b]n, in the uniform distribution membership query learning setting, where both b and n are “large”. We obtain -time algorithms for the following classes: •-way Majority of -dimensional rectangles.•Union of many -dimensional rectangles.•-way Majority of -Or of disjoint dimensional rectangles. Our main algorithmic tool is an extension of Jackson’s boosting- and Fourier-based Harmonic Sieve algorithm [J.C. Jackson, An efficient membership-query algorithm for learning with respect to the uniform distribution, Journal of Computer and System Sciences 55 (3) (1997) 414–440] to the domain [b]n, building on work of Akavia et al. [A. Akavia, S. Goldwasser, S. Safra, Proving hard core predicates using list decoding, in: Proc. of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’03, 2003, pp. 146–156]. Other ingredients used to obtain the results stated above are techniques from exact learning [A. Beimel, E. Kushilevitz, Learning boxes in high dimension, Algorithmica 22 (1/2) (1998) 76–90] and ideas from recent work on learning augmented circuits [J.C. Jackson, A.R. Klivans, R.A. Servedio, Learnability beyond , in: Proc. of the 34th Annual ACM Symposium on Theory of Computing, STOC ’02, 2002, pp. 776–784] and on representing Boolean functions as thresholds of parities [A.R. Klivans, R.A. Servedio, Learning in time , Journal of Computer and System Sciences 68 (2) (2004) 303–318].