Lower Bound Techniques in Property Testing

As with other areas of computer science, lower bounds play an essential role in the field of property testing. The question can be posed as follows. Given a black-box access to an arbitrary function which is to be tested against a property, how many queries are necessary to be made to the function so that with high probability the function can be distinguished between having the property and ϵ-away from all the functions having the property.

The tester can be both adaptive and non-adaptive. The most efficient and generic tool for proving lower bounds for property testing was given by Yao. We will look at the statement and proof of these tools and their application in proving lower bounds of the query complexity of testing k-linearity and monotonicity.

References:

[BK12]  Eric Blais and Daniel M. Kane. Tight bounds for testing k-linearity. In Anupam Gupta, Klaus Jansen, Jos´e D. P. Rolim, and Rocco A. Servedio, editors, APPROX-RANDOM, volume 7408 of Lecture Notes in Computer Science, pages 435–446. Springer, 2012.

[FLN+02] Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex Samorodnitsky. Monotonicity testing over general poset domains. In John H. Reif, editor, STOC, pages 474–483. ACM, 2002.

[Yao77] Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). In FOCS, pages 222–227. IEEE Computer Society, 1977.