On distribution-specific learning with membership queries versus pseudorandom generation
On distribution-specific learning with membership queries versus pseudorandom generation
Johannes Köbler and Wolfgang Lindner
Abstract:
Abstract:
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.
Ps-File: On distribution-specific learning with membership queries versus pseudorandom generation
zuletzt geändert:
31.10.05
SV
Document Actions
Persönliche Werkzeuge
- Sie sind nicht eingeloggt.
- Seite bearbeiten
Deutsch
English