Algebraic testing and weight distributions of codes

✍ Scribed by M. Kiwi

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 296 KB
• Volume: 299
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00816-2

✦ Synopsis

We study the testing problem, that is, the problem of determining (maybe probabilistically) if a function to which one has oracle access satisÿes 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 ÿnite ÿelds.

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 satisÿes the property of interest.