Abstract

We study the testing problem, that is, the problem of determining (maybe probabilistically) if a function to which one has oracle access satisfies a given property. We propose a framework in which to formulate and carry out the analysis of several known tests. This framework establishes a connection between testing and the theory of weight distributions of codes. We illustrate this connection by giving a coding theoretic interpretation of several tests that fall under the label of low-degree tests. We also show how the connection naturally suggests a new way of testing for linearity over finite fields. We derive from the MacWilliams Theorems a general result, the Duality Testing Lemma, and use it to analyze the simpler tests that fall into our framework. In contrast to other analyses of tests, the ones we present elicit the fact that a test's probability of rejecting a function depends on how far away the function is from every function that satisfies the property of interest. © 2002 Published by Elsevier Science B.V.