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

be the list of all.

The Walsh-Hadamard code that are linear functions on the finite field.

.-bit string.

Properties

. 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