Approximating hyper-rectangles: Learning and pseudorandom sets

The PAC learning of rectangles has been studied because they have been foun d experimentally to yield excellent hypotheses for several applied learning problems. Also, pseudorandom sets for rectangles have been actively studie d recently because (i) they are a subproblem common to the derandomization of depth-2 (DNF) circuits and derandomizing randomized logspace, and (ii) t hey approximate the distribution of n independent multivalued random variab les. We present improved upper bounds for a class of such problems of "appr oximating" high-dimensional rectangles that arise in PAC learning and pseud orandomness. (C) 1998 Academic Press.