TR10-108 Authors: Eli Ben-Sasson, Madhu Sudan

Publication: 9th July 2010 18:37

Downloads: 2684

Keywords:

A linear code is said to be affine-invariant if the coordinates of the code can be viewed as a vector space and the code is invariant under an affine transformation of the coordinates. A code is said to be locally testable if proximity of a received word

to the code can be tested by querying the received word in a few coordinates.

Locally testable codes have played a critical role in the construction of probabilistically checkable proofs and most such codes originate from simple affine invariant codes (in particular the Reed-Muller codes). Furthermore it turns out that the local testability of these codes can really be attributed to their affine-invariance. It was hoped that by studying broader classes of affine-invariant

codes, one may find nicer, or simpler, locally testable codes, and in particular improve (significantly) on the rate achieved

by Reed-Muller codes.

In this work we show that low-rate is an inherent limitation of

affine-invariant codes.

We show that any $k$-query affine-invariant

binary code is contained in an $2^k$-query testable Reed-Muller code.

In fact our result shows that any affine-invariant code that has

a $k$-local constraint (i.e., a weight $k$ codeword in its dual),

a necessary condition for $k$-query local

testability, is contained in a Reed-Muller code that is

$2^k$-locally characterized (i.e., its dual is spanned by

words of weight at most $2^k$).

While the structure of affine-invariant codes has been explored

quite extensively in the recent past [Kaufman and Sudan 2008; Grigorescu et al. 2008, 2009], relating the locality of constraints in such codes to the rate

has been a non-trivial challenge. Such questions lead

to the task of showing that a class of systems of multivariate

polynomial equations have no common zeroes over finite fields.

Our result effectively shows a certain class of such systems

(subclasses of diagonal systems) that have no common zeroes.