CS369E: Communication Complexity (for Algorithm Designers) Lecture #8: Lower Bounds in Property Testing∗

We begin in this section with a brief introduction to the field of property testing. Section 2 explains the famous example of “linearity testing. ” Section 3 gives upper bounds for the canonical problem of “monotonicity testing, ” and Section 4 shows how to derive property testing lower bounds from communication complexity lower bounds.1 These lower bounds will follow from our existing communication complexity toolbox (specifically, Disjoint-ness); no new results are required. Let D and R be a finite domain and range, respectively. In this lecture, D will always be {0, 1}n, while R might or might not be {0, 1}. A property is simply a set P of functions from D to R. Examples we have in mind include: 1. Linearity, where P is the set of linear functions (with R a field and D a vector space over R). 2. Monotonicity, where P is the set of monotone functions (with D and R being partially ordered sets). 3. Various graph properties, like bipartiteness (with functions corresponding to charac-teristic vectors of edge sets, with respect to a fixed vertex set). 4. And so on. The property testing literature is vast. See [14] for a starting point