|
NeuroCOLT
Technical Report NC-TR-97-024
Approximating
Hyper-Rectangles: Learning and Pseudo-random Sets
Peter
Auer
Technische Universitaet Graz, Austria
Philip
Long
National University of Singapore, Singapore
Aravind
Srinivasan
National University of Singapore, Singapore
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.
Download Compressed Postscript
|