Cryptographic hardness of distribution-specific learning

S1 .50 to separate the PAC learning model from the absolute mist ake-bound model of learning. Kearns and Valiant [15] used specific public key encryption schemes to prove the unpredictability of NCl circuits (which are equivalent to Boolean formulas); using prediction preserving reductions of Pitt and Warmuth [22] they proved the unpredictability of deterministic finite acceptors and several other important classes. Angluin and Kharitonov [4] used chosen ciphertext secure public key encryption and secure digital signatures to prove similar results for prediction with membership queries. While these recent results were important in proving hardness of distribution-free learning, their common drawback is that distributions of examples used for this purpose were cryptographically orient ed and unnatural. The possibility of using "malicious" distributions to show non-learnability highlighted the fact that the distribution independence requirement makes PAC learning of relatively simple concepts very difficult. At the same time, significant progress has been achieved in constructing learning algorithms that work well on specific distributions. This is especially true for the uniform distribution. Linial, Mansour, and Nisan [19] used Fourier analysis to construct a 0(2'Og" d') algorithm (for some constant a) to learn Boolean circuits of depth d on the uniform distribution. Several improvements and extensions of this result followed, in some cases reducing both sample and time complexity and extending it to product distributions, though the running time of resulting algorithms remained superpolynomial. Very recently Mansour [21] used Fourier analysis to obtain a O(nlOg 10gn ) algorithm for learning DNF Boolean formulas with membership queries on the uniform distribution. These successful efforts to construct learning algorithms that perform relatively well on the uniform distribution motivated our investigation of the cryptographic limitations on learning on specific distributions.