On distribution-specific learning with membership queries versus pseudorandom generation

Johannes K\"obler Wolfgang Lindner

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


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 also for non-adaptive membership queries and for any (non-trivial) p-samplable distribution.


Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Maintainer fsttcs20@cse.iitd.ernet.in.
Start Conference Manager
Conference Systems