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.