[Colloquium] Talk by David Xiao, Princeton University on May 11, 2009

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Monday, May 11, 2009
Time: 3:45 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:	David Xiao

From:		Princeton University

Website: 	http://www.cs.princeton.edu/~dxiao/

Title:      On the Black-box Complexity of PAC Learning

Abstract:    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.

Refreshments will be served prior to the talk in RY 255.