Learning Unions of ω(1)-Dimensional Rectangles Authors: Alp Atıcı and Rocco A. Servedio Source: Algorithmic Learning Theory, 17th International Conference, ALT 2006, Barcelona, October 2006, Proceedings, (José L. Balcázar, Phil Long and Frank Stephan, Eds.), Lecture Notes in Artificial Intelligence 4264, pp. 32 - 47, Springer 2006. Abstract. 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 poly(n, log b)-time algorithms for the following classes: Our main algorithmic tool is an extension of Jackson's boosting- and Fourier-based Harmonic Sieve algorithm [Jackson 1997] to the domain [b]n, building on work of [Akavia, Goldwasser, Safra 2003]. Other ingredients used to obtain the results stated above are techniques from exact learning [Beimel, Kushilevitz 1998] and ideas from recent work on learning augmented AC0 circuits [Jackson, Klivans, Servedio 2002] and on representing Boolean functions as thresholds of parities [Klivans, Servedio 2001]. ©Copyright 2006, Springer