Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-067 | 4th May 2014 14:53

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



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