Abstract
Johannes Köbler and Wolfgang Lindner
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.