Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-072 | 14th July 2000 00:00

Approximating Hyper-Rectangles: Learning and Pseudo-random Sets

RSS-Feed




TR00-072
Authors: Peter Auer, Philip M. Long, Aravind Srinivasan
Publication: 12th September 2000 20:24
Downloads: 1476
Keywords: 


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 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.



ISSN 1433-8092 | Imprint