We suggest a new approach to obtain bounds on locally correctable and some locally testable binary linear codes, by arguing that these codes (or their subcodes) have coset leader graphs with high discrete Ricci curvature.
The bounds we obtain for locally correctable codes are worse than the best known bounds obtained using quantum information theory, but are better than those obtained using other methods, such as the "usual" information theory. (We remark that our methods are completely elementary.)
The bounds we obtain for a family of locally testable codes improve the best known bounds.
1. Abstract.
2. Page 2, first line of Remark 1.1
3. Page 4, in third paragraph after Definition 1.7 (see also the footnote).
4. Page 10, in third paragraph in the proof of Theorem 1.2: replaced 'dividing out by...' by 'contracting' - this is simply more correct.
We suggest a new approach to obtain bounds on locally correctable and some locally testable binary linear codes, by arguing that their coset leader graphs have high discrete Ricci curvature.
The bounds we obtain for locally correctable codes are worse than the best known bounds obtained using quantum information theory, but are better than those obtained using other methods, such as the "usual" information theory. (We remark that our methods are completely elementary.)
The bounds we obtain for a family of locally testable codes improve the best known bounds.