__
TR97-010 | 2nd April 1997 00:00
__

#### Testing and Weight Distributions of Dual Codes

**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.