Long code (mathematics)

Short description: Computational theory

Math logic
Classification
Type	Block code
Block length	[math]\displaystyle{ 2^{n} }[/math] for some [math]\displaystyle{ n\in\N }[/math]
Message length	[math]\displaystyle{ \log n }[/math]
Alphabet size	[math]\displaystyle{ 2 }[/math]
Notation	[math]\displaystyle{ (2^{n},\log n)_2 }[/math]-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 [math]\displaystyle{ f_1,\dots,f_{2^n} : \{0,1\}^k\to \{0,1\} }[/math] for [math]\displaystyle{ k=\log n }[/math] be the list of all functions from [math]\displaystyle{ \{0,1\}^k\to\{0,1\} }[/math]. Then the long code encoding of a message [math]\displaystyle{ x\in\{0,1\}^k }[/math] is the string [math]\displaystyle{ f_1(x)\circ f_2(x)\circ\dots\circ f_{2^n}(x) }[/math] where [math]\displaystyle{ \circ }[/math] denotes concatenation of strings. This string has length [math]\displaystyle{ 2^n=2^{2^k} }[/math].

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

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

Properties

The long code does not contain repetitions, in the sense that the function [math]\displaystyle{ f_i }[/math] computing the [math]\displaystyle{ i }[/math]th bit of the output is different from any function [math]\displaystyle{ f_j }[/math] computing the [math]\displaystyle{ j }[/math]th bit of the output for [math]\displaystyle{ j\neq i }[/math]. 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.