Cryptographic Lower Bounds for Learnability of Boolean Functions on the Uniform Distribution

AbstractWe 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 × n1 + ϵ subset sum is hard, we construct (using the results of lmpagliazzo and Naor and Goldreich, Goldwasser, and Micali) 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 × 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 × (1 + ϵ)n subset sum is hard, we show that the class of NC circuits can not be learned with nlogcn samples for any constant c