Revision #1 Authors: Tali Kaufman, Shachar Lovett

Accepted on: 10th November 2010 13:14

Downloads: 2859

Keywords:

The Weil bound for character sums is a deep result in Algebraic Geometry with many applications both in mathematics and in the theoretical computer science. The Weil bound states that for any polynomial $f(x)$ over a finite field $\F$ and any additive character $\chi:\F \to \C$, either $\chi(f(x))$ is a constant function or it is distributed close to uniform. The Weil bound is quite effective as long as $\deg(f) \ll \sqrt{|\F|}$, but it breaks down when the degree of $f$ exceeds $\sqrt{|\F|}$. As the Weil bound plays a central role in many areas, finding extensions for polynomials of larger degree is an important problem with many possible applications.

In this work we develop such an extension over finite fields $\F_{p^n}$ of small characteristic: we prove that if $f(x)=g(x)+h(x)$ where $\deg(g) \ll \sqrt{|\F|}$ and $h(x)$ is a sparse polynomial of arbitrary degree but bounded weight degree, then the same conclusion of the classical Weil bound still holds: either $\chi(f(x))$ is constant or its distribution is close to uniform. In particular, this shows that the subcode of Reed-Muller codes of degree $\omega(1)$ generated by traces of sparse polynomials is a code with near optimal distance, while Reed-Muller of such a degree has no distance (i.e. $o(1)$ distance) ; this is one of the few examples where one can prove that sparse polynomials behave differently from non-sparse polynomials of the same degree.

As an application we prove new general results for affine invariant codes. We prove that any affine-invariant subspace of quasi-polynomial size is (1) indeed a code (i.e. has good distance) and (2) is locally testable. Previous results for general affine invariant codes were known only for codes of polynomial size, and of length $2^n$ where $n$ needed to be a prime. Thus, our techniques are the first to extend to general families of such codes of super-polynomial size, where we also remove the requirement from $n$ to be a prime. The proof is based on two main ingredients: the extension of the Weil bound for character sums, and a new Fourier-analytic approach for estimating the weight distribution of general codes with large dual distance, which may be of independent interest.

(1) Fixed a mistake: the result holds only for affine invariant codes of up to quasi-polynomial size (and not exponential size, as was claimed in the first draft).

(2) Added a proof that in this regime all affine invariant codes are indeed codes (i.e. have good distance).

TR10-065 Authors: Tali Kaufman, Shachar Lovett

Publication: 13th April 2010 11:54

Downloads: 1985

Keywords:

In this work we consider linear codes which are locally testable

in a sublinear number of queries. We give the first general family

of locally testable codes of exponential size. Previous results of

this form were known only for codes of quasi-polynomial size (e.g.

Reed-Muller codes). We accomplish this by showing that any affine

invariant code $\mathcal{C}$ over $\mathbb{F}_{p^n}$ of size $p^{p^{\Omega(n)}}$

is locally testable using $poly(\log_p{|\mathcal{C}|}/n)$ queries.

Previous general result for affine invariant codes were known only

for sparse codes, i.e. codes of size $p^{O(n)}$. The main new

ingredients used in our proof are a new extension of the Weil bound for character

sums, and a Fourier-analytic approach for estimating the weight

distribution of affine invariant codes.