Meir code[1] 

Description

Locally testable \([n,k,d]_q\) code with query complexity \(\text{poly}(\log k)\) and rejection ratio \(R/n = 1/\text{poly}(\log k)\). Code construction is probabilistic and combinatorial.

Parent

  • \(q\)-ary linear LTC — Meir codes stand out in that they are based on a combinatorial construction, while other LTCs often use algebraic tools.

Cousin

References

[1]
O. Meir, “Combinatorial construction of locally testable codes”, Proceedings of the fortieth annual ACM symposium on Theory of computing 285 (2008) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: meir

Cite as:
“Meir code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/meir
BibTeX:
@incollection{eczoo_meir, title={Meir code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/meir} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/meir

Cite as:

“Meir code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/meir

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/distributed_storage/ltc/meir.yml.