Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
On Distribution-Specific Learning with Membership Queries versus Pseudorandom Generation
Ist Teil von
FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science, 2000, p.336-347
Ort / Verlag
Berlin, Heidelberg: Springer Berlin Heidelberg
Erscheinungsjahr
2000
Link zum Volltext
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
We consider a weak version of pseudorandom function generators and show that their existence is equivalent to the non-learnability of Boolean circuits in Valiant’s pac-learning model with membership queries on the uniform distribution. Furthermore, we show that this equivalence holds still for the case of non-adaptive membership queries and for any (non-trivial) p-samplable distribution.