Name
Abstract | ||
|---|---|---|
Locally testable codes (LTCs) of constant minimum (absolute) distance that allow the tester to make a nearly linear number of queries have become the focus of attention recently, due to their connections to central questions in approximability theory. In particular, the binary Reed-Muller code of block length N and absolute distance d is known to be testable with O(N/d) queries, and has a dimension of ≈ 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 ≈ 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, the authors of [HRZS13] and [GKS13] 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.5555/2722129.2722216 | SODA |
DocType | Volume | ISBN |
Journal | 21 | 978-1-61197-433-1 |
Citations | PageRank | References |
1 | 0.35 | 22 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Guruswami | 1 | 3205 | 247.96 |
| Madhu Sudan | 2 | 5616 | 591.68 |
| Ameya Velingker | 3 | 35 | 4.95 |
| Carol Wang | 4 | 28 | 4.19 |