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.

Math logic
Classification
Type	Block code
Block length	${\displaystyle 2^{n}}$ for some ${\displaystyle n\in \mathbb {N} }$
Message length	${\displaystyle \log n}$
Alphabet size	${\displaystyle 2}$
Notation	${\displaystyle (2^{n},\log n)_{2}}$-code

Definition

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

The Walsh-Hadamard code is a subcode of the long code, and can be obtained by only using functions ${\displaystyle f_{i}}$ that are linear functions when interpreted as functions ${\displaystyle \mathbb {F} _{2}^{k}\to \mathbb {F} _{2}}$ on the finite field with two elements. Since there are only ${\displaystyle 2^{k}}$ such functions, the block length of the Walsh-Hadamard code is ${\displaystyle 2^{k}}$.

An equivalent definition of the long code is as follows: The Long code encoding of ${\displaystyle j\in [n]}$ is defined to be the truth table of the Boolean dictatorship function on the ${\displaystyle j}$th coordinate, i.e., the truth table of ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$ with ${\displaystyle f(x_{1},\dots ,x_{n})=x_{j}}$.[1] Thus, the Long code encodes a ${\displaystyle (\log n)}$-bit string as a ${\displaystyle 2^{n}}$-bit string.

Properties

The long code does not contain repetitions, in the sense that the function ${\displaystyle f_{i}}$ computing the ${\displaystyle i}$th bit of the output is different from any function ${\displaystyle f_{j}}$ computing the ${\displaystyle j}$th bit of the output for ${\displaystyle 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

1. Definition 7.3.1 in Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)