Computer Science/Discrete Mathematics Seminar I

Property testing considers the following general question: how many queries to some combinatorial object (e.g., a boolean function or a graph) do we need to determine whether the object has some property P or whether it is "far" from having the property P? Over the last two decades, much effort has been spent on studying the query complexity for testing properties of boolean functions. This effort has led to many results for specific properties, and has also yielded a variety of techniques for designing property testing algorithms. Yet, in the case of lower bounds, few general techniques are known beyond the use of Yao's Minimax Lemma. In this talk, we will introduce a simple reduction from communication problems to property testing problems. With this reduction, we obtain new lower bounds for a number of fundamental problems in property testing from known lower bounds in communication complexity. In particular, we will show how this technique gives improved lower bounds for testing monotonicity, k-linearity, juntas, and decision tree complexity. This is joint work with Joshua Brody and Kevin Matulef.