Long code (mathematics)

In theoretical computer science and coding theory, the long code is an error-correcting code that is locally decodable. Long codes have an extremely poor rate, but play a fundamental role in the theory of hardness of approximation.

In theoretical computer science and coding theory, the long code is an error-correcting code that is locally decodable. Long codes have an extremely poor rate, but play a fundamental role in the theory of hardness of approximation. ==Definition== Let f_1,\dots,f_{2^n} : \{0,1\}^k\to \{0,1\} for k=\log n be the list of all functions from \{0,1\}^k\to\{0,1\} . Then the long code encoding of a message x\in\{0,1\}^k is the string f_1(x)\circ f_2(x)\circ\dots\circ f_{2^n}(x) where \circ denotes concatenation of strings. This string has length 2^n=2^{2^k} . The Walsh-Hadamard code is a subcode of the long code, and can be obtained by only using functions f_i that are linear functions when interpreted as functions \mathbb F_2^k\to\mathbb F_2 on the finite field with two elements. Since there are only 2^k such functions, the block length of the Walsh-Hadamard code is 2^k . An equivalent definition of the long code is as follows: The Long code encoding of j\in[n] is defined to be the truth table of the Boolean dictatorship function on the j th coordinate, i.e., the truth table of f:\{0,1\}^n\to\{0,1\} with f(x_1,\dots,x_n)=x_j . Thus, the Long code encodes a (\log n) -bit string as a 2^n -bit string. ==Properties== The long code does not contain repetitions, in the sense that the function f_i computing the i th bit of the output is different from any function f_j computing the j th bit of the output for j\neq i . Among all codes that do not contain repetitions, the long code has the longest possible output. Moreover, it contains all non-repeating codes as a subcode. ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1190987351 under CC BY-SA 4.0; modifications have been made.