Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > INFORMATION VS. EFFICIENT COMPUTATION:
Reports tagged with Information vs. Efficient Computation:
TR97-028 | 12th July 1997
Scott E. Decatur, Oded Goldreich, Dana Ron

Computational Sample Complexity


In a variety of PAC learning models, a tradeoff between time and
information seems to exist: with unlimited time, a small amount of
information suffices, but with time restrictions, more information
sometimes seems to be required.
In addition, it has long been known that there are
concept classes ... more >>>




ISSN 1433-8092 | Imprint