Goldreich-Sudan code[1] 

Description

Locally testable \([n,k,d]\) code with \(n = k^{1+O(1/u)}\) and distance of order \(\Omega(n)\) for query complexity \(u\). The same work also presented a probabilistic construction of codes of size \(k^{1+o(1)}\).

Parent

  • Binary linear LTC — Goldreich-Sudan codes resulted from what is often referred to as the first systematic study of LTCs.

Cousin

References

[1]
O. Goldreich and M. Sudan, “Locally testable codes and PCPs of almost-linear length”, Journal of the ACM 53, 558 (2006) DOI
Page edit log

Your contribution is welcome!

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

edit on this site

Zoo Code ID: gs-ltc

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

Cite as:

“Goldreich-Sudan code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/gs-ltc

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/ltc/gs-ltc.yml.