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.

k = log ⁡ n

be the list of all functions from

Then the long code encoding of a message

is the string

denotes concatenation of strings.

This string has length

The Walsh-Hadamard code is a subcode of the long code, and can be obtained by only using functions

that are linear functions when interpreted as functions

on the finite field with two elements.

such functions, the block length of the Walsh-Hadamard code is

An equivalent definition of the long code is as follows: The Long code encoding of

is defined to be the truth table of the Boolean dictatorship function on the

th coordinate, i.e., the truth table of

[1] Thus, the Long code encodes a

( log ⁡ n )

-bit string as a

The long code does not contain repetitions, in the sense that the function

computing the

th bit of the output is different from any function

computing the

th bit of the output for

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.