Description
Nonlinear locally testable code of extremely large length that is not practical, but is useful for certain probabilistically checkable proof (PCP) constructions [4].
For \(x\in\mathbb{F}_2^k\), the long-code encoding of \(x\) is the binary string \begin{align} \mathrm{Long}(x)=\left(f(x)\right)_{f:\mathbb{F}_2^k\to\mathbb{F}_2}~, \tag*{(1)}\end{align} whose coordinates are indexed by all Boolean functions on \(\mathbb{F}_2^k\). Thus, the code has length \(2^{2^k}\) and \(2^k\) codewords.
Protection
Any two distinct codewords differ on exactly half of the coordinates, so the minimum distance is \(2^{2^k-1}\).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
References
- [1]
- M. Bellare, O. Goldreich, and M. Sudan, “Free bits, PCPs and non-approximability-towards tight results”, Proceedings of IEEE 36th Annual Foundations of Computer Science 422 DOI
- [2]
- J. Håstad, “Some optimal inapproximability results”, Journal of the ACM 48, 798 (2001) DOI
- [3]
- M. Bellare, O. Goldreich, and M. Sudan, “Free Bits, PCPs, and Nonapproximability—Towards Tight Results”, SIAM Journal on Computing 27, 804 (1998) DOI
- [4]
- P. Harsha et al., “Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)”, (2010) arXiv:1002.3864
Page edit log
- Victor V. Albert (2022-09-30) — most recent
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.