文章基本信息

标题：Computational Sample Complexity
本地全文：下载
作者：Scott E. Decatur ; Oded Goldreich ; Dana Ron 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 that can be learned in the absence of computational restrictions, but (under standard cryptographic assumptions) cannot be learned in polynomial time regardless of sample size. Yet, these results do not answer the question of whether there are classes for which learning from a small set of examples is infeasible, but becomes feasible when the learner has access to (polynomially) more examples.
关键词：Computational Learning Theory, Error Correcting Codes, Information vs. Efficient Computation, Pseudo-Random Functions, The Wire-Tap Channel Problem