Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-067 | 4th May 2014 14:53

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

RSS-Feed

Abstract:

Locally testable codes (LTCs) of constant distance that allow the tester to make a linear number of queries have become the focus of attention recently, due to their elegant connections to hardness of approximation. In particular, the binary Reed-Muller code of block length N and distance d is known to be testable with O(N/d) queries, and has a dimension of \approx N - (\log N)^{\log d}. The polylogarithmically small co-dimension is the basis of constructions of small set expanders with many ``bad'' eigenvalues, and size-efficient PCPs based on a shorter version of the long code. The smallest possible co-dimension for a distance d code (without any testability requirement) is \approx \frac{d}{2} \log N, achieved by BCH codes. This raises the natural question of understanding where in the spectrum between the two classical families, Reed-Muller and BCH, the optimal co-dimension of a distance d LTC lies --- in other words the ``price'' one has to pay for local testability.

One promising approach for constructing LTCs is to focus on affine-invariant codes, whose structure makes testing guarantees easier to deduce than for general codes. Along these lines, Guo et al. and Haramaty et al. recently constructed an affine-invariant family of high-rate LTCs with slightly smaller co-dimension than Reed-Muller codes. In this work, we show that their construction is essentially optimal among linear affine-invariant LTCs that contain the Reed-Muller code of the appropriate degree.



ISSN 1433-8092 | Imprint