Next: Collision-Free Hashing from Lattice
Up: Sabbatical at MIT (1996-1998)
Previous: On the Circuit Complexity
It is shown that there exists a universal learning algorithm
that PAC-learns every concept class within complexity that
is linearly related to the complexity of the best learning
algorithm for this class.
This observation is derived by an adaptation,
to the learning context,
of Levin's proof of the existence of optimal algorithms for NP.
Comments:
Authored by O. Goldreich and D. Ron. Appeared in
- IPL, Vol. 63, 1997, pages 131-136.
Oded Goldreich
2003-07-30