Long code (mathematics) explained

Math logic
Block Length:	2 ^{n} for some n\in\N
Message Length:	log n
Alphabet Size:	2
Notation:	( 2 ^{n} , log n) _{2} -code

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,...,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...\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 F ^{k\to 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,...,x} _{n)=x} _{j} .^[1] 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 ≠ 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.

Notes and References

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