Details

Autor(en) / Beteiligte

• Köbler, Johannes
• Lindner, Wolfgang

Titel

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.