Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-023 | 6th February 2018 21:29

On coset leader graphs of structured linear codes

RSS-Feed




Revision #1
Authors: Eran Iceland, Alex Samorodnitsky
Accepted on: 6th February 2018 21:29
Downloads: 797
Keywords: 


Abstract:

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.



Changes to previous version:

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.


Paper:

TR18-023 | 4th February 2018 21:54

On coset leader graphs of structured linear codes





TR18-023
Authors: Eran Iceland, Alex Samorodnitsky
Publication: 5th February 2018 17:37
Downloads: 916
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint