Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-132 | 11th September 2021 07:11

Pseudo-random functions and uniform learnability


Authors: Eric Binnendyk
Publication: 12th September 2021 10:27
Downloads: 97


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