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.

Definition

Let $f_1,\dots,f_ : \^k\to \$ for $k=\log n$ be the list of ''all'' functions from $\^k\to\$.
Then the long code encoding of a message $x\in\^k$ is the string $f_1(x)\circ f_2(x)\circ\dots\circ f_(x)$ where $\circ$ denotes concatenation of strings.
This string has length $2^n=2^$.

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 /math> is defined to be the truth table of the Boolean dictatorship function on the $j$th coordinate, i.e., the truth table of $f:\^n\to\$ with $f(x_1,\dots,x_n)=x_j$.Definition 7.3.1 i
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
/ref>
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

{{reflist

Coding theory
Error detection and correction