Long code (mathematics)

---

title: "Long code (mathematics)" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["coding-theory", "error-detection-and-correction"] description: "Computational theory" topic_path: "general/coding-theory" source: "https://en.wikipedia.org/wiki/Long_code_(mathematics)" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Computational theory ::

::data[format=table title="infobox code"]

Field	Value
name	Math logic
type	Block code
block_length	2^{n} for some n\in\N
message_length	\log n
alphabet_size	2
notation	(2^{n},\log n)_2-code
::

| name = Math logic | image = | image_caption = | namesake = | type = Block code | block_length = 2^{n} for some n\in\N | message_length = \log n | rate = | distance = | 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,\dots,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\dots\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 \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[n] is defined to be the truth table of the Boolean dictatorship function on the jth coordinate, i.e., the truth table of f:{0,1}^n\to{0,1} with f(x_1,\dots,x_n)=x_j. 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 ith bit of the output is different from any function f_j computing the jth 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

References

1. Definition 7.3.1 in [https://arxiv.org/abs/1002.3864 Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)]

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::