Lower Bounds Techniques
Oded Goldreich · Cambridge University Press eBooks · 2017
: We present and illustrate three techniques for proving lower bounds on the query complexity of property testers. 1. Showing a pair of distributions, one on instances that have the property and the other on instances that are far from the property, such that an oracle machine of low query complexity cannot distinguish these two distributions. 2. Showing a reduction from communication complexity. That is, showing that a communication complexity problem of high complexity can be solved within communication complexity that is related to the query complexity of the property testing task that we are interested in. 3. Showing a reduction from another testing problem. That is, showing a “local” reduction of a hard testing problem to the testing problem that we are interested in. We also present simplifications of these techniques for the cases of onesided error probability testers and nonadaptive testers. The methodology of reducing from communication complexity was introduced by Blais, Brody, and Matulef [54], and our description of it is based on [136]. Introduction Our perspective in this book is mainly algorithmic. Hence, we view complexity lower bounds mainly as justifications for the failure to provide better algorithms (i.e., algorithms of lower complexity). The lower bounds that we shall be discussing are lower bounds on the query complexity of testers. These lower bounds are of an information theoretic nature, and so they cannot (and do not) rely on computational assumptions. We start with two brief preliminary discussions. The first discussion is very abstract and vague: it concerns the difficulty of establishing lower bounds. The second discussion is very concrete: it highlights the fact that computational complexity considerations play no role in this chapter, a fact that is most evident in the avoidance of the uniformity condition. What Makes Lower Bounds Hard to Prove? Proving lower bounds is often more challenging than proving upper bounds, since one has to defeat all possible methods (or algorithms) rather than show that one of them works. Indeed, it seems harder to cope with a universal quantifier than with an existential one, but one should bear in mind that a second quantifier of opposite nature follows the first one.