Seminar: May 11, 2009

David Xiao, Princeton University

On the Black-box Complexity of PAC Learning

The PAC model (Valiant, CACM ’84) is one of the central models studied in computational learning theory. There is evidence that many specific classes of functions (e.g. intersections of half- spaces, parity functions with noise, etc.) are hard to learn by efficient algorithms, and cryptographic assumptions imply that learning small circuits is hard. We say that PAC learning is hard if no efficient algorithm can learn all functions computable by small circuits.

In this talk, we show that the black-box complexity of PAC learning lies strictly between NP and ZK. More precisely, if P = NP then PAC learning is easy and if ZK !=BPP then PAC learning is hard, but black- box techniques (with some additional restrictions) do not suffice to prove equivalence in either case.

With regard to NP, we rule out non-adaptive reductions using a PAC learning oracle to solve an NP-complete problem by showing this would imply that coNP in contained in AM, which is considered implausible.

With regard to ZK, we rule out relativizing proofs that ZK !=BPP based on hardness of learning. Using the characterization of ZK of Ong and Vadhan (EUROCRYPT ’07), we also show that any black-box construction of a (computational) ZK protocol for a language L based on hardness of learning implies that L actually has a statistical zero knowledge proof (i.e. L is in SZK), and hence such a black-box construction is unlikely to exist for NP-complete languages.

Parts of this talk are based on joint work with Benny Applebaum and Boaz Barak.