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.

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

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.