ECCC-Report TR14-067https://eccc.weizmann.ac.il/report/2014/067Comments and Revisions published for TR14-067en-usSun, 04 May 2014 14:54:46 +0300
Paper TR14-067
| Limitations on Testable Affine-Invariant Codes in the High-Rate Regime |
Venkatesan Guruswami,
Madhu Sudan,
Ameya Velingker,
Carol Wang
https://eccc.weizmann.ac.il/report/2014/067Locally 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.Sun, 04 May 2014 14:54:46 +0300https://eccc.weizmann.ac.il/report/2014/067