Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > AFFINE INVARIANT CODES:
Reports tagged with affine invariant codes:
TR10-065 | 13th April 2010
Tali Kaufman, Shachar Lovett

Testing of exponentially large codes, by a new extension to Weil bound for character sums

Revisions: 1

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




ISSN 1433-8092 | Imprint