Title: Property Testing Lower Bounds via Communication Complexity Speaker: Kevin Matulef Affiliation: IIIS, Tsinghua University. Date: May 8, 2011 Abstract: We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing communication problems to testing problems, thus allowing us to use known lower bounds in communication complexity to prove lower bounds in testing. This scheme is general and implies a number of new testing bounds, as well as simpler proofs of several known bounds. In this talk we will illustrate our technique by proving lower bounds for testing juntas, k-linearity, monotonicity, and more. Based on joint work with Eric Blais and Joshua Brody.