Name
Title | ||
|---|---|---|
On Distribution-Specific Learning with Membership Queries versus Pseudorandom Generation |
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. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/3-540-44450-5_27 | FSTTCS |
Keywords | Field | DocType |
pseudorandom function generator,pac-learning model,uniform distribution,weak version,boolean circuit,p-samplable distribution,membership query,distribution-specific learning,non-adaptive membership query,computational learning theory,pac learning | Pseudorandom function family,Boolean function,Discrete mathematics,Boolean circuit,Pseudorandom generators for polynomials,Computer science,Equivalence (measure theory),Pseudorandom generator,Pseudorandom generator theorem,Pseudorandom number generator | Conference |
Volume | ISSN | ISBN |
1974 | 0302-9743 | 3-540-41413-4 |
Citations | PageRank | References |
0 | 0.34 | 19 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Johannes Köbler | 1 | 580 | 46.51 |
| Wolfgang Lindner | 2 | 23 | 3.38 |