Abstract:
As data sets become larger, it becomes more and more impractical to analyze them in their entirety, whenever one wishes to extract a small piece of information. The field of Property Testing is concerned with analyzing large objects (say a large function or graph), with only very limited query access to the object itself. The goal is to determine, approximately, whether the large object has a given property, while minimizing the fraction of the object the algorithm must look at. Testing algorithms have been discovered for a large number of different properties. But traditionally, lower bounds for such algorithms have not been easy to prove. In 2011, Blais, Brody, and Matulef described a simple scheme for proving lower bounds by reducing communication problems to testing problems, thereby leveraging several known lower bounds in communication complexity. This technique has yielded a number of new lower bounds, as well as simpler proofs of previously known bounds. We will descrive the BBM technique, and survey some of the subsequent applications.

Based on joint with Eric Blais, Joshua Brody, and Chenggang Wu.

Biography:
Kevin is currently a postdoc at Aarhus University as part of CTIC. From 2011-2012 he was a member of the technical staff at 10gen working on MongoDB. From 2009-2011 he was a postdoctoral researcher at ITCS, part of the IIIS at Tsinghua University in Beijing.

In 2009, he obtained his Ph.D. from the Department of Mathematics at MIT, where he was also a member of the Theory of Computation group in CSAIL. While in graduate school he frequently visited the Columbia University CS department.

He obtained a Certificate of Advanced Study in Mathematics from Cambridge University, and a Bachelor of Science from Brown University.