Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Humboldt-Universität zu Berlin | Mathematisch-Naturwissenschaftliche Fakultät | Institut für Informatik | Komplexität und Kryptografie | Publikationen | Abstracts | 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:

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