Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Philip M. Long:

TR00-072 | 14th July 2000
Peter Auer, Philip M. Long, Aravind Srinivasan

Approximating Hyper-Rectangles: Learning and Pseudo-random Sets

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

TR00-067 | 13th July 2000
Peter Auer, Philip M. Long

Simulating Access to Hidden Information while Learning

We introduce a new technique which enables a learner without access to
hidden information to learn nearly as well as a learner with access to
hidden information. We apply our technique to solve an open problem
of Maass and Turan, showing that for any concept class F the least ... more >>>

TR00-050 | 13th July 2000
Peter Auer, Philip M. Long, Gerhard J. Woeginger

On the Complexity of Function Learning

The majority of results in computational learning theory
are concerned with concept learning, i.e. with the special
case of function learning for classes of functions
with range {0,1}. Much less is known about the theory of
learning functions with a larger range such
as N or R. In ... more >>>

ISSN 1433-8092 | Imprint