ECCC-Report TR21-132https://eccc.weizmann.ac.il/report/2021/132Comments and Revisions published for TR21-132en-usSat, 16 Oct 2021 22:59:48 +0300
Revision 1
| Pseudo-random functions and uniform learnability |
Eric Binnendyk
https://eccc.weizmann.ac.il/report/2021/132#revision1Boolean circuits are a model of computation. A class of Boolean circuits is called a polynomial class if the number of nodes is bounded by a polynomial function of the number of input variables. A class $C_n[s(n)]$ of Boolean functions is called learnable if there are algorithms that can approximate functions in $C_n[s(n)]$ when given oracle access to the function. A distribution $D$ of functions is called pseudorandom against a circuit class $C[t(n)]$ if any oracle circuit $C^f$ from $C[t(n)]$ outputs 1 with the same probability if the oracle $f$ is chosen from $D$ as it would if the oracle were random. It is known that a polynomial class of circuits is learnable if and only if it contains no pseudorandom distributions of functions. However, there is no known algorithm to produce the learner given the number of inputs the circuits have (the learner is non-uniform). I investigate a uniform version of the min-max theorem as a possible tool to find an algorithm for such learners.
Sat, 16 Oct 2021 22:59:48 +0300https://eccc.weizmann.ac.il/report/2021/132#revision1
Paper TR21-132
| Pseudo-random functions and uniform learnability |
Eric Binnendyk
https://eccc.weizmann.ac.il/report/2021/132Boolean circuits are a model of computation. A class of Boolean circuits is called a polynomial class if the number of nodes is bounded by a polynomial function of the number of input variables. A class $C_n[s(n)]$ of Boolean functions is called learnable if there are algorithms that can approximate functions in $C_n[s(n)]$ when given oracle access to the function. A distribution $D$ of functions is called pseudorandom against a circuit class $C[t(n)]$ if any oracle circuit $C^f$ from $C[t(n)]$ outputs 1 with the same probability if the oracle $f$ is chosen from $D$ as it would if the oracle were random. It is known that a polynomial class of circuits is learnable if and only if it contains no pseudorandom distributions of functions. However, there is no known algorithm to produce the learner given the number of inputs the circuits have (the learner is non-uniform). I investigate a uniform version of the min-max theorem as a possible tool to find an algorithm for such learners.
Sun, 12 Sep 2021 10:27:36 +0300https://eccc.weizmann.ac.il/report/2021/132