REPORTS > DETAIL:

### Paper:

TR14-067 | 4th May 2014 14:53

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

TR14-067
Authors: Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang
Publication: 4th May 2014 14:54
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.