Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/99195
Title: Approximating hyper-rectangles: Learning and pseudorandom sets
Authors: Auer, P.
Long, P.M. 
Srinivasan, A. 
Keywords: Approximations of distributions
Derandomization
Explicit constructions
Machine learning
Multiple-instance learning
PAC learning
Pseudorandomness
Ramsey graphs
Random graphs
Rectangles
Sample complexity
Issue Date: Dec-1998
Source: Auer, P.,Long, P.M.,Srinivasan, A. (1998-12). Approximating hyper-rectangles: Learning and pseudorandom sets. Journal of Computer and System Sciences 57 (3) : 376-388. ScholarBank@NUS Repository.
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. © 1998 Academic Press.
Source Title: Journal of Computer and System Sciences
URI: http://scholarbank.nus.edu.sg/handle/10635/99195
ISSN: 00220000
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

39
checked on Mar 9, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.