We investigate cryptographic limitations on the power of membership queries to help with concept learning. We extend the notion of prediction-preserving reductions to prediction with membership queries. We exhibit a number of reductions and show several prediction problems to be complete for different complexity classes. We show that assuming the intractability of (1) quadratic residues module a composite, (2) inverting RSA encryption, or (3) factoring Blum integers, there is no polynomial time prediction algorithm with membership queries for Boolean formulas, constant depth threshold circuits, 3 μ-Boolean formulas, finite unions or intersections of DFAs, 2-way DFAs, NFAs, or CFGs. Also, we show that if there exist one-way functions that cannot be inverted by polynomial-sized circuits, then CNF or DNF formulas and convex polytopes intersected with the Boolean hypercube are either polynomial time predictable without membership queries, or they are not polynomial time predictable even with membership queries; so, in effect, membership queries will not help with predicting CNF or DNF formulas.

We investigate cryptographic lower bounds on the learn-

We investigate cryptographic lower bounds on the number of samples and on computational resources required to learn several classes of boolean circuits on the uniform distribution. Under the assumption that solving n x n1+ε subset sum is hard, we construct (using the results of Impagliazzo and Naor [IN89] and Goldreich, Goldwasser, and Micali[GGM86] a pseudo-random function generator that can be computed by shallow boolean circuits. From this we conclude that learning AC1 circuits on the uniform distribution requires Ω(nlog log n) different samples, or, alternatively, that learning AC1 circuits on the uniform distribution with a polynomial number of samples is as hard as solving n x n1+ε subset sum. We also show that no algorithm can learn NC1 circuits on the uniform distribution with a polynomial number of samples. Using the weaker assumption that solving n x (1+ε)nsubset sum is hard, we show that the class of NC circuits can not be learned with nlogcn samples for any c.

We investigate cryptographic limitations on the power of membership queries to help with concept learning.

Computational resources necessary to generate pseudorandom strings are studied. In particular, lower bounds are proved for pseudorandom number generators, whereas previous research concentrated on upper bounds. The idea of separation of machine-based complexity classes on the basis of their ability (or inability) to generate pseudorandom strings is introduced and investigated.>