Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR21-132 | 16th October 2021 22:59

Pseudo-random functions and uniform learnability

RSS-Feed




Revision #1
Authors: Eric Binnendyk
Accepted on: 16th October 2021 22:59
Downloads: 4
Keywords: 


Abstract:

Boolean 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.



Changes to previous version:

Added references for the definitions in circuit complexity, pseudorandomness, and learnability used in the paper, as well as the theorems used.


Paper:

TR21-132 | 11th September 2021 07:11

Pseudo-random functions and uniform learnability





TR21-132
Authors: Eric Binnendyk
Publication: 12th September 2021 10:27
Downloads: 100
Keywords: 


Abstract:

Boolean 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.



ISSN 1433-8092 | Imprint