P. Auer, P. M. Long and A. Srinivasan.
Approximating hyper-rectangles:
learning and pseudorandom sets. Journal of Computer and
System Sciences, 57(3):376-388, 1998.
(Available in Postscript and PDF formats.)
Abstract
The PAC learning of rectangles has been studied
because they have been found experimentally
to yield excellent hypotheses
for several applied learning problems. Also, pseudorandom sets for
rectangles have been
actively studied recently because (i) they are a subproblem common to the
derandomization of depth-2 (DNF)
circuits and derandomizing Randomized Logspace, and (ii) they
approximate the distribution
of n independent multivalued random variables. We present improved
upper bounds for a class of
such problems of "approximating" high-dimensional rectangles that arise
in PAC learning and pseudorandomness.