Abstract:
We study the testing problem, that is, the problem of determining (maybe probabilistically) if a function to which we have oracle access satisfies a given property. We propose a framework in which to formulate and carry out the analyzes of several known tests. This framework establishes a connection between testing and the theory of weight distributions of dual 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 coding theoretic connection we establish naturally suggests a new way of testing for linearity over finite fields. There are two important parameters associated to every test. The first one is the test's probability of rejecting the claim that the function to which it has oracle access satisfies a given property. The second one is the distance from the oracle function to any function that satisfies the property of interest. The goal when analyzing tests is to explain the relationship between these two parameters. There are several good reasons why good analyzes are worth striving for. For example, improved analyzes of a family of tests referred to as low-degree tests, typically translate into improved construction of probabilistically checkable proofs and better hardness of approximation results. 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. The analyzes 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. Other standard ways of addressing the testing problem do not capture this intuition. We discuss the apparent benefits and limitations of our approach to the testing problem and contrast it to the ones found in the literature.