[Jump to code hierarchy]

Long code[1,2]

Description

Locally testable \([2^{2^k},k,d]\) code. The encoder maps a \(k\)-bit string into a codeword that consists of the values of all Boolean functions on the \(k\)-bit string. The code is not practical, but is useful for certain probabilistically checkable proof (PCP) constructions [3].

Cousin

  • Hadamard code— The Hadamard code is a subcode of the long code and can be obtained by restricting the long-code construction to only linear functions.

Member of code lists

Primary Hierarchy

Classical Domain
Binary Kingdom
Binary codeECC
Binary group-orbit codeECC
Linear binary codeLinear \(q\)-ary Linear code over \(\mathbb{Z}_q\) ECC
Binary linear LTCLinear \(q\)-ary LTC ECC
Parents
Binary linear LTC
Long code

References

[1]
J. Håstad, “Some optimal inapproximability results”, Journal of the ACM 48, 798 (2001) DOI
[2]
M. Bellare, O. Goldreich, and M. Sudan, “Free Bits, PCPs, and Nonapproximability---Towards Tight Results”, SIAM Journal on Computing 27, 804 (1998) DOI
[3]
P. Harsha et al., “Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)”, (2010) arXiv:1002.3864
Page edit log

Your contribution is welcome!

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

edit on this site

Zoo Code ID: long

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

Cite as:

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

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