For random variables

Every code of distance \(d\) over an alphabet of size \(q\) has rate \(R\) at most

where \(e = \lfloor (d-1)/2 \rfloor \).

The Hamming code \([2^r-1,2^r-r-1,3]_2\) is a perfect code: it meets the Hamming bound for \(d=3\) codes with equality.

Let \(q \ge 3\) be an integer and \(0 \le \rho \le 1 - 1/q\). Then for any integer \(m \ge 2\),

Let \(\mathscr {C}\) be an infinite family of \(q\)-ary codes with relative distance \(0 \le \delta \le 1 - \frac{1}{q}\) and rate \(R\). Then

The field \(\mathbb {F}_{p^s}\) is \(\mathbb {F}_p[X]/E(X)\), where \(E(X)\) is an irreducible polynomial of degree \(s\).

There is a Las Vegas algorithm (Algorithm 126) to generate an irreducible polynomial of degree \(s\) over any \(\mathbb {F}_q\) in expected time \(\mathrm{poly}(s, \log q)\).

Reed-Solomon codes are MDS codes.

For \(0\le p{\lt}\tfrac 12\), the capacity of \(\mathrm{BSC}_p\) is \(1-H(p)\).

Suppose \(\beta _1,\dots ,\beta _n \ge 0\) are such that the polynomial \(\beta (X)\) of Definition 174 satisfies \(\beta (i) \le 0\) for all \(i = d,d+1,\dots ,n\). Then every binary code of minimum distance at least \(d\) has size at most \(\beta (0)\).

The concatenated code \(C^*\) of Definition 210 is an asymptotically good code and is strongly explicit.

There are explicit codes of relative distance \((1-\varepsilon )\) and rate \(\Omega (\varepsilon )\), over an alphabet of size \(2^{O(1/\varepsilon )}\).

Suppose there exist \(c \in \mathbb {Z}_+\), \(\alpha {\gt} c/2\) and \(\gamma ,\rho {\gt} 0\) such that \(\{ G_i\} _{i\in \mathbb {Z}_+}\) is a \((c,\gamma ,\alpha )\)-bipartite expander with \(G_i\) having \(n_i\) left vertices, \(m_i\) right vertices with \(m_i/n_i {\lt} 1-\rho \) for every \(i \in \mathbb {Z}_+\). Then the family of codes \(\{ C(G_i)\} _{i\in \mathbb {Z}_+}\) is asymptotically good.

For every \(\delta \in [0,1]\) and \(\varepsilon {\gt} 0\) there exists an explicit family of binary linear (Tanner) codes of rate at least \(1-2h(\sqrt\delta )\) and relative distance at least \(\delta - \varepsilon \). Consequently, for every \(\tau {\gt} 0\) there exists an explicitly constructible family of asymptotically good Tanner codes of rate \(R \ge 1-\tau \) and distance \(\delta = \Omega (\tau ^2/\log ^2(1/\tau ))\).

There are explicit binary linear codes that lie within \(\varepsilon \) of the Zyablov bound and can be constructed in time polynomial in the block length and exponential in \(\mathrm{poly}(1/\varepsilon )\).

For every

If

Under the hypotheses of Lemma 327, there exists a value \(\)θ^* [0,1]\( such that Algorithm \ref{alg:c14-gmd-v2} run with \)θ\( fixed to \)θ^*\( in Step 1 produces \)y”\( with \)2e’ + s’ < D\( (and hence, by Theorem \ref{thm:c14-rs-errors-erasures} as instantiated for \)D_C_out\(, correctly outputs \)m\(). \begin{proof} \uses{lem:c14-gmd-v2-expectation} By Lemma \ref{lem:c14-gmd-v2-expectation}, \end{proof}\)E_θ[2e’+s’] < D\( where the expectation is over \)θ\( chosen uniformly in \)[0,1]\(. If every \)θ[0,1]\( produced \)2e’(θ) + s’(θ) ≥D\(, then the expectation would be at least \)D\(, a contradiction. Hence there exists \)θ^* [0,1]\( with \)2e’(θ^*) + s’(θ^*) < D\(. \)

Using the code

For every input

The set of solutions to

is contained in an affine subspace

For any integer

The polynomial hash family

There is a deterministic

There is a deterministic

For every

For \(\)0 ≤p ≤1\(, let \)D_p\( denote the distribution on \){0,1}^n\( where each bit is picked independently with probability \)p\( of being \)1\(. The average-case Gap Hamming problem asks: given an \)x {0,1}^n\( sampled from either \)D_1/3\( or \)D_2/3\(, determine which distribution \)x\( was sampled from. \)

Let

Let

A decision problem \(\)L\( is in \)NP\( (a promise problem \)(Y,N)\( is in \)promise-NP\(, respectively) if there is a polynomial time verification algorithm \)R\( such that: \begin{itemize} \item if \end{itemize}\)x L\( (resp. \)x Y\(), there exists a string \)y\(, of size polynomial in \)|x|\(, such that \)R(x,y)\( returns \textsc{Yes}; \item if \)x L\( (resp. \)x N\(), then for every string \)y\( of size polynomial in \)|x|\(, \)R(x,y)\( returns \textsc{No}. \)

A decision problem \(\)L\( is in the complexity class \)P\( if there is an algorithm solving \)L\( whose worst-case run time on inputs of size \)N\( is \)O(N^c)\( for some fixed constant \)c ≥0\( (a polynomial time algorithm). Likewise, a promise problem \)(Y,N)\( is in \)promise-P\( if there is a polynomial time algorithm solving \)(Y,N)\(. \)

Without loss of generality, the input to a decision problem is

Given a vector

We say

We say

Given \(\)n\( linear equations over \)k\( variables, all over \)F_2\( (i.e. all variables lie in \){0,1}\( and all arithmetic is over the binary field \)F_2\(: addition is XOR and multiplication is AND), and an integer \)0 ≤s ≤n\(, find a solution to the system that satisfies at least \)s\( of the \)n\( equations. We denote this problem \)MaxLinearEq(k,n,s)\(, dropping the arguments to refer to the problem in general. \)

Given a graph \(\)G = (V,E)\( with \)|V| = k\( and \)|E| = n\(, and an integer \)0 ≤s ≤n\(, does there exist a cut of size at least \)s\(, i.e. a subset \)S ⊂V\( such that the number of edges with one endpoint in \)S\( and the other in \)V ∖S\( is at least \)s\(? We call this problem \)MaxCut(k,n,s)\(. \)

A decision problem

A decision problem

A promise problem is defined by a pair of disjoint non-empty subsets

In the RAM model of computation, for an input with

A randomized algorithm is an algorithm (in the RAM model, modified so that a register can be loaded with independent uniform random bits in one step) whose behavior may depend on internal random bits even for a fixed input. Its run time

We say

Let

Given a bivariate polynomial

Given a finite field

A sequence of vectors

A set

Let

Given polynomials

A matrix

Given a set

A vector of length

A set

The input to the root-finding problem is a polynomial

We say that a polynomial

Let

Let

Over a field

The conditional mutual information between

For random variables

Let

Let

The mutual information between random variables

A binary code \(C \subseteq \{ 0,1\} ^n\) of dimension \(k\) is called a binary linear code if there is a \(k\times n\) matrix \(G\) over \(\{ 0,1\} \) (addition being XOR, multiplication being AND) such that \(C = \{ \mathbf x \cdot G \mid \mathbf x \in \{ 0,1\} ^k\} \), and, writing \(C(\mathbf x) \overset {\mathrm{def}}{=} \mathbf x \cdot G\) (viewing \(\mathbf x\) as a row vector), the map \(\mathbf x \mapsto C(\mathbf x)\) is a bijection from \(\{ 0,1\} ^k\) onto \(C\). The matrix \(G\) is called a generator matrix for \(C\).

A code of block length \(n\) over an alphabet \(\Sigma \) is a subset \(C \subseteq \Sigma ^n\). We use \(q\) to denote the alphabet size \(|\Sigma |\) (which need not be a constant and may depend on \(n\)).

Equivalently, writing \(|C| = M\), we may view \(C\) as a mapping

where \([M] \overset {\mathrm{def}}{=} \{ 1,2,\dots ,M\} \); this is the convention we use whenever we speak of “the codeword corresponding to message \(\mathbf m\),” written \(C(\mathbf m)\).

Let \(\{ n_i\} _{i\ge 1}\) be an increasing sequence of block lengths and suppose there exist sequences \(\{ k_i\} _{i\ge 1}\), \(\{ d_i\} _{i \ge 1}\) and \(\{ q_i\} _{i\ge 1}\) such that for all \(i \ge 1\) there exists an \((n_i,k_i,d_i)_{q_i}\) code \(C_i\). Then the sequence \(\mathscr C = \{ C_i\} _{i\ge 1}\) is a family of codes. The rate of \(\mathscr C\) is

when the limit exists. The relative distance of \(\mathscr C\) is

when the limit exists. If \(q_i = q\) for all \(i \ge 1\), then \(\mathscr C\) is referred to as a family of \(q\)-ary codes.

Let \(C \subseteq \Sigma ^n\) be a code. A mapping \(D : \Sigma ^n \to [|C|]\) is called a decoding function for \(C\).

Given a code \(C \subseteq \Sigma ^n\) with \(|\Sigma |=q\), its dimension is

An algorithm related to a code of block length \(n\) is called efficient if it runs in time polynomial in \(n\). (Throughout the book, unless mentioned otherwise, a “code” implicitly refers to a family of codes, so that asymptotic run time as \(n \to \infty \) is meaningful.)

Let \(C \subseteq \Sigma ^n\). An encoding function for \(C\) is an injective map \(E : [|C|] \to \Sigma ^n\) whose image is \(C\).

Let \(C \subseteq \Sigma ^n\) be a code and let \(t \ge 1\) be an integer. \(C\) is said to be a \(t\)-erasure-correcting code if there exists a decoding function \(D\) such that for every message \(\mathbf m \in [|C|]\) and every \(t\)-erasure channel \(\mathrm{Ch}\) we have \(D(\mathrm{Ch}(C(\mathbf m))) = \mathbf m\).

Let \(C \subseteq \Sigma ^n\) be a code and let \(t \ge 1\) be an integer. \(C\) is said to be a \(t\)-error-correcting code if there exists a decoding function \(D\) such that for every message \(\mathbf m \in [|C|]\) and every \(t\)-error channel \(\mathrm{Ch}\) we have \(D(\mathrm{Ch}(C(\mathbf m))) = \mathbf m\).

Let \(C \subseteq \Sigma ^n\) be a code and let \(t \ge 1\) be an integer. \(C\) is said to be a \(t\)-error-detecting code if there exists a detecting procedure \(D\) such that for every message \(\mathbf m\) and every received vector \(\mathbf v \in \Sigma ^n\) satisfying \(\Delta (C(\mathbf m),\mathbf v) \le t\), it holds that \(D\) outputs \(1\) if \(\mathbf v = C(\mathbf m)\) and \(0\) otherwise; i.e.

For any vector \(\mathbf x \in [q]^n\) and integer \(e \ge 0\), the Hamming ball of radius \(e\) centered at \(\mathbf x\) is

The Hamming code \(C_H\) is the binary code of block length \(7\) with message length \(4\) defined, for \((x_1,x_2,x_3,x_4) \in \{ 0,1\} ^4\), by

It has parameters \(q=2\), \(k=4\), \(n=7\), \(R=4/7\).

Given two vectors \(\mathbf u, \mathbf v \in \Sigma ^n\), the Hamming distance between \(\mathbf u\) and \(\mathbf v\), denoted \(\Delta (\mathbf u,\mathbf v)\), is the number of positions in which \(\mathbf u\) and \(\mathbf v\) differ. The relative Hamming distance is

Let \(q \ge 2\). Given a vector \(\mathbf v \in \{ 0,1,\dots ,q-1\} ^n\), its Hamming weight, denoted \(\mathrm{wt}(\mathbf v)\), is the number of non-zero symbols in \(\mathbf v\).

Let \(C \subseteq \Sigma ^n\). The minimum distance (or just distance) of \(C\), denoted \(\Delta (C)\), is

The relative minimum distance of \(C\) is

Given a code \(C \subseteq \Sigma ^n\), the maximum likelihood decoding (MLD) function \(D_{MLD} : \Sigma ^n \to C\) outputs, for every received word \(\mathbf y \in \Sigma ^n\), a codeword closest to \(\mathbf y\) in Hamming distance (with ties broken arbitrarily):

A code \(C \subseteq \Sigma ^n\) with dimension \(k\) and distance \(d\) is called an \((n,k,d)_\Sigma \) code, also written an \((n,k,d)_{|\Sigma |}\) code.

A code that meets the Hamming bound of Theorem 32 with equality is called a perfect code: i.e. an \((n,k,d)_q\) code \(C\) is perfect if

Equivalently, the Hamming balls of radius \(e\) centered at the codewords of \(C\) partition the entire ambient space \([q]^n\). The \((7,4,3)_2\) Hamming code \(C_H\) (Definition 22) is an example of a perfect code, since \(2^4 = 2^7/(7+1)\).

The rate of a code with dimension \(k\) and block length \(n\) is

Since \(k \le n\) (and we always assume \(k{\gt}0\), \(n{\lt}\infty \)), we have \(0 {\lt} R \le 1\).

An \(n\)-symbol \(t\)-Erasure Channel over the alphabet \(\Sigma \) is a function \(\mathrm{Ch} : \Sigma ^n \to (\Sigma \cup \{ ?\} )^n\) that satisfies \(\Delta (\mathbf v,\mathrm{Ch}(\mathbf v)) \le t\) for every \(\mathbf v \in \Sigma ^n\) (viewing both arguments of \(\Delta (\cdot ,\cdot )\) as elements of \((\Sigma \cup \{ ?\} )^n\)), and such that for every \(i\in [n]\) with \(\mathbf v_i \neq \mathrm{Ch}(\mathbf v)_i\) we have \(\mathrm{Ch}(\mathbf v)_i = {?}\). A coordinate \(i\) with \(\mathrm{Ch}(\mathbf v)_i = {?}\) is called an erasure.

An \(n\)-symbol \(t\)-Error Channel over the alphabet \(\Sigma \) is a function \(\mathrm{Ch} : \Sigma ^n \to \Sigma ^n\) that satisfies \(\Delta (\mathbf v, \mathrm{Ch}(\mathbf v)) \le t\) for every \(\mathbf v \in \Sigma ^n\).

Let \(H\) be a parity check matrix of a code \(C\). The code generated by \(H\) is called the dual of \(C\), and is denoted \(C^\perp \). If \(C\) is an \([n,k]_q\) code, then \(C^\perp \) is an \([n,n-k]_q\) code, directly from the definition.

A field \(\mathbb {F}\) is given by a triple \((S,+,\cdot )\), where \(S\) is the set of elements and \(+,\cdot \) are functions \(S\times S \to S\) such that:

• \((S,+)\) forms a commutative group with identity element \(0\in S\).

• \((S\setminus \{ 0\} ,\cdot )\) forms a commutative group with identity element \(1\in S\setminus \{ 0\} \).

• \(\cdot \) distributes over \(+\): for every \(a,b,c\in S\), \(a\cdot (b+c) = a\cdot b + a\cdot c\).

A finite field is a field \(\mathbb {F} = (S,+,\cdot )\) whose set of elements \(S\) is finite. We write \(|\mathbb {F}| = |S|\) for its size, and denote a finite field of size \(q\) by \(\mathbb {F}_q\).

If \(C\) is an \([n,k]_q\) linear code then there exists a matrix \(G\in \mathbb {F}_q^{k\times n}\) of rank \(k\) satisfying

\(G\) is referred to as a generator matrix of \(C\): the code \(C\) is the set of all possible linear combinations of the rows of \(G\). Neither the generator matrix nor the parity check matrix of a code is unique; however, all generator matrices of \(C\) have the same \(k\times n\) dimensions. (We also allow matrices \(M\in \mathbb {F}_q^{m\times n}\) that are not of full row rank to generate a code \(C=\{ \mathbf{x}\cdot M \mid \mathbf{x}\in \mathbb {F}_q^m\} \), though we reserve the phrase “generator matrix” for full rank matrices.)

A group \(\mathbb {G}\) is given by a pair \((S,\circ )\), where \(S\) is the set of elements and \(\circ \) is a function \(S\times S \to S\) satisfying:

• Closure: for every \(a,b\in S\), \(a\circ b \in S\).

• Associativity: for every \(a,b,c\in S\), \(a\circ (b\circ c) = (a\circ b)\circ c\).

• Identity: there exists a special element \(e\in S\) such that for every \(a \in S\), \(a\circ e = e \circ a = a\).

• Inverse: for every \(a \in S\) there exists a unique \(a^{-1}\in S\) such that \(a\circ a^{-1} = a^{-1}\circ a = e\).

If \(\mathbb {G}=(S,\circ )\) satisfies all properties except the existence of inverses then \(\mathbb {G}\) is called a monoid. \(\mathbb {G}\) is commutative if for every \(a,b\in S\), \(a\circ b = b \circ a\).

For a positive integer \(r\), the Hadamard Code \(C_{Had,r}\) is the code generated by the \(r\times 2^r\) matrix \(\overline{\mathbf{H}}_r\) obtained by adding an all-zero column to (say, in front of the columns of) \(\mathbf{H}_r\).

For any positive integer \(r\), define the matrix \(\mathbf{H}_r \in \mathbb {F}_2^{r\times (2^r-1)}\) to be the \(r\times (2^r-1)\) matrix whose \(i\)th column \(\mathbf{H}_r^i\) is the binary representation of \(i\), for \(1\le i \le 2^r-1\) (a vector in \(\{ 0,1\} ^r\)).

The \([2^r-1, 2^r-r-1]_2\) Hamming code, denoted \(C_{H,r}\), is the code with parity check matrix \(\mathbf{H}_r\). In other words,

Let \(q\) be a prime power (i.e. \(q=p^s\) for some prime \(p\) and integer \(s\ge 1\)). \(C\subseteq \mathbb {F}_q^n\) is a linear code if it is a linear subspace of \(\mathbb {F}_q^n\). If \(C\) has dimension \(k\) and distance \(d\) then it is referred to as an \([n,k,d]_q\), or just an \([n,k]_q\), code.

Vectors \(\mathbf{v}_1,\dots ,\mathbf{v}_k \in \mathbb {F}_q^n\) are linearly independent if for every \(1\le i \le k\) and every \((k-1)\)-tuple \((a_1,\dots ,a_{i-1},a_{i+1},\dots ,a_k)\in \mathbb {F}_q^{k-1}\),

In other words, \(\mathbf{v}_i\) is not in the span of \(\{ \mathbf{v}_1,\dots ,\mathbf{v}_{i-1},\mathbf{v}_{i+1},\dots ,\mathbf{v}_k\} \) for every \(1\le i \le k\). The vectors are linearly dependent if they are not linearly independent.

A non-empty subset \(S \subseteq \mathbb {F}_q^n\) is a linear subspace if the following hold:

1. For every \(\mathbf{x},\mathbf{y}\in S\), \(\mathbf{x}+\mathbf{y}\in S\) (vector addition over \(\mathbb {F}_q\), done componentwise).

2. For every \(a\in \mathbb {F}_q\) and \(\mathbf{x}\in S\), \(a\cdot \mathbf{x}\in S\) (componentwise scalar multiplication over \(\mathbb {F}_q\)).

The rank of a matrix in \(\mathbb {F}_q^{k\times n}\) is the maximum number of linearly independent rows (equivalently, the maximum number of linearly independent columns). A matrix in \(\mathbb {F}_q^{k\times n}\) with rank \(\min (k,n)\) is said to have full rank.

If \(C\) is an \([n,k]_q\) linear code then there exists a matrix \(H\in \mathbb {F}_q^{(n-k)\times n}\) of rank \(n-k\) satisfying

\(H\) is referred to as a parity check matrix of \(C\). All parity check matrices of \(C\) have the same \((n-k)\times n\) dimensions.

For a positive integer \(r\), the Simplex Code \(C_{Sim,r}\) is the code generated by \(\mathbf{H}_r\). Equivalently, \(C_{Sim,r} = C_{H,r}^\perp \).

Given a set \(B = \{ \mathbf{v}_1,\dots ,\mathbf{v}_\ell \} \subseteq \mathbb {F}_q^n\), the span of \(B\) is the set of vectors

A vector space \(V\) over a field \(\mathbb {F}\) is given by a triple \((T,+,\cdot )\) such that \((T,+)\) forms a commutative group and \(\cdot \), referred to as the scalar product, is a function \(\mathbb {F}\times T \to T\) such that for every \(a,b\in \mathbb {F}\) and \(\mathbf{u},\mathbf{v}\in T\): \((a+b)\cdot \mathbf{u} = a\cdot \mathbf{u} + b\cdot \mathbf{u}\) and \(a\cdot (\mathbf{u}+\mathbf{v}) = a\cdot \mathbf{u} + a\cdot \mathbf{v}\).

Given two events \(A\) and \(B\) defined over the same domain and probability distribution, the probability of \(A\) conditioned on \(B\) is

Let \(q \ge 2\) and \(n \ge r \ge 1\) be integers. The volume of a Hamming ball of radius \(r\) is given by

(The choice of \(\mathbf{0}\) as center is immaterial: the volume of a Hamming ball is independent of its center, as the sum on the right makes clear, so any point may serve as center.)

Two random variables \(A\) and \(B\) are called independent if for every \(a, b\) in the ranges of \(A\) and \(B\) respectively,

Since \(H_q(\cdot )\) restricted to the domain \([0, 1-1/q]\) is a bijective map onto \([0,1]\), we define \(H_q^{-1}(y) = x\) for the unique \(x \in [0, 1-1/q]\) such that \(H_q(x) = y\).

Given a finite domain \(\mathbb {D}\), a probability distribution is a function

An event \(\mathbb {E}\) is a predicate on \(\mathbb {D}\), equivalently a subset of \(\mathbb {D}\).

Given probability distributions \(p_1\) and \(p_2\) over domains \(\mathbb {D}_1\) and \(\mathbb {D}_2\) respectively, the product distribution \(p_1 \times p_2\) over \(\mathbb {D}_1 \times \mathbb {D}_2\) is the distribution under which every element \((x,y) \in \mathbb {D}_1 \times \mathbb {D}_2\) is picked by choosing \(x\) from \(\mathbb {D}_1\) according to \(p_1\) and \(y\) is picked independently from \(\mathbb {D}_2\) according to \(p_2\).

Let \(q\) be an integer with \(q \ge 2\) and let \(x\) be a real number with \(0 \le x \le 1\). The \(q\)-ary entropy function is defined by

For the special case \(q = 2\) we drop the subscript and write \(H(x) = H_2(x) = -x \log x - (1-x)\log (1-x)\), where \(\log \) denotes \(\log _2\) (the convention used throughout the book). The maximum value of \(H_q\) is \(1\), achieved at \(x = 1 - 1/q\).

Let \(\mathbb {D}\) be a finite domain, \(I \subset \mathbb {R}\) a finite subset, and \(p\) a probability distribution over \(\mathbb {D}\). A random variable is a function \(V : \mathbb {D} \to I\). Its expectation is defined as

For an event \(E\) over \(\mathbb {D}\), its indicator variable \(\mathbb {1}_E : \mathbb {D} \to \{ 0,1\} \) is defined by \(\mathbb {1}_E(x) = 1\) if \(x \in E\) and \(0\) otherwise.

The uniform distribution over a finite domain \(\mathbb {D}\), denoted \(\mathscr {U}_{\mathbb {D}}\), is given by

Let \(V\) be a random variable. Its variance is defined as

and its standard deviation is \(\sigma [V] = \sqrt{\mathrm{Var}[V]}\).

An infinite family \(\mathscr {C}\) of \(q\)-ary codes (for \(q\) either a fixed constant or allowed to grow with the block length) is called asymptotically good if both its rate \(R = R(\mathscr {C})\) and its relative distance \(\delta = \delta (\mathscr {C})\) are bounded away from \(0\), i.e., \(R(\mathscr {C}) {\gt} 0\) and \(\delta (\mathscr {C}) {\gt} 0\). The results of this chapter (in particular the Gilbert–Varshamov bound, Theorem 105, and the Plotkin bound, Theorem 111) determine for which pairs \((R,\delta )\) such families can and cannot exist.

For every subset of indices \(S \subseteq [n]\) of size exactly \(k\) and a code \(C \subseteq \Sigma ^n\), \(C_S\) is the set of all codewords in \(C\) projected onto the indices in \(S\).

A polynomial \(F(X)\) is irreducible if for every \(G_1(X), G_2(X)\) such that \(F(X) = G_1(X) G_2(X)\), we have \(\min (\deg (G_1), \deg (G_2)) = 0\).

An \((n,k,d)_q\) code is called Maximum Distance Separable (MDS) if \(d = n-k+1\).

\(\alpha \in \mathbb {F}_q\) is a root of a polynomial \(F(X)\) if \(F(\alpha ) = 0\).

A polynomial over a variable \(X\) and a finite field \(\mathbb {F}_q\) is given by a finite sequence \((f_0, f_1, \ldots , f_d)\) with \(f_i \in \mathbb {F}_q\), denoted \(F(X) = \sum _{i=0}^{d} f_i X^i\). The degree of \(F(X)\), denoted \(\deg (F)\), is the largest index \(i\) such that \(f_i \neq 0\). The set \(\mathbb {F}_q[X]\) of all such polynomials, with the usual coefficientwise addition and convolution multiplication, forms a commutative ring.

Given a polynomial \(F(X) \in \mathbb {F}_q[X]\) and \(\alpha \in \mathbb {F}_q\), the evaluation of \(F(X)\) at \(\alpha \), denoted \(F(\alpha )\), is \(\sum _{i=0}^{\deg F} f_i \alpha ^i \in \mathbb {F}_q\). (More generally, if \(\alpha \) lies in an extension field \(\mathbb {F}_Q \supseteq \mathbb {F}_q\), the evaluation \(F(\alpha ) \in \mathbb {F}_Q\) is defined the same way.)

Let \(\mathbb {F}_q\) be a finite field, and choose \(n\) and \(k\) satisfying \(k \leq n \leq q\). Fix a sequence \(\alpha = (\alpha _1, \alpha _2, \ldots , \alpha _n)\) of \(n\) distinct elements (evaluation points) from \(\mathbb {F}_q\). The encoding function of the Reed-Solomon code \(\mathrm{RS}_q[\alpha , k] : \mathbb {F}_q^k \to \mathbb {F}_q^n\) maps a message \(m = (m_0, m_1, \ldots , m_{k-1})\) with \(m_i \in \mathbb {F}_q\) to the degree-\((k-1)\) polynomial

and then outputs

We write simply \(\mathrm{RS}\) when \(q\), \(\alpha \), \(k\) are clear from context, and call the image \(\{ \mathrm{RS}[m] \mid m \in \mathbb {F}_q^k\} \) the Reed-Solomon code, or RS code. A common special case is \(n = q - 1\) with evaluation points \(\mathbb {F}_q^* = \mathbb {F}_q \setminus \{ 0\} \).

Let \(0\le \alpha \le 1\). The Binary Erasure Channel with erasure probability \(\alpha \), denoted \(\mathrm{BEC}_\alpha \), is the stochastic channel with \(\mathcal{X}=\{ 0,1\} \), \(\mathcal{Y}=\{ 0,1,{?}\} \) (where \({?}\) denotes an erasure), and transition matrix given by

and \(\mathbf{M}(x,y)=0\) for every other pair \((x,y)\). That is, every transmitted bit is erased with probability \(\alpha \) and left unchanged with probability \(1-\alpha \).

Let \(\sigma \ge 0\). The Binary Input Additive Gaussian White Noise Channel with standard deviation \(\sigma \), denoted \(\mathrm{BIAGWN}_\sigma \), is the (continuous) channel with input alphabet \(\mathcal{X}=\{ -1,1\} \) and output alphabet \(\mathcal{Y}=\mathbb {R}\), in which for \((x,y)\in \{ -1,1\} \times \mathbb {R}\) the noise \(y-x\) is distributed according to the Gaussian distribution with mean \(0\) and standard deviation \(\sigma \), i.e.

Let \(0\le p\le 1\). The Binary Symmetric Channel with crossover probability \(p\), denoted \(\mathrm{BSC}_p\), is the stochastic channel with \(\mathcal{X}=\mathcal{Y}=\{ 0,1\} \) and transition matrix

That is, every transmitted bit is flipped independently with probability \(p\). (One may restrict attention to \(0\le p\le \tfrac 12\), since reliable communication over \(\mathrm{BSC}_p\) for \(p\le \tfrac 12\) implies reliable communication over \(\mathrm{BSC}_{p'}\) for \(p'{\gt}\tfrac 12\).) For the rest of the chapter, \(\mathbf{e}\sim \mathrm{BSC}_p\) denotes an error pattern \(\mathbf{e}\in \{ 0,1\} ^n\) drawn according to the error distribution induced by \(\mathrm{BSC}_p\).

Given a stochastic channel, its capacity is a real number \(C\ge 0\) such that reliable communication is possible over the channel if and only if the rate is less than \(C\). That is: for every rate \(R{\lt}C\), there is a family of codes (with associated encoding and decoding functions) of rate \(R\) whose decoding error probability is negligible (indeed \(2^{-\Omega (n)}\)); and for every rate \(R{\gt}C\), for every choice of encoding and decoding functions of rate \(R\), there is some message for which the decoding error probability is bounded below by a constant.

Fix a stochastic channel and a pair of encoding and decoding functions \((E,D)\) for a code of block length \(n\). The decoding error probability of \((E,D)\) is a function \(f(n)\) such that for every message \(\mathbf{m}\), the decoding algorithm recovers \(\mathbf{m}\) with probability at least \(1-f(n)\) (the probability taken over the randomness of the channel noise), where \(\lim _{n\to \infty }f(n)=0\), i.e. \(f(n)=o(1)\). Ideally one would like \(f(n)=2^{-\Omega (n)}\).

A code \(C\) of block length \(n\) is called explicit if there exists a \(\mathrm{poly}(n)\)-time algorithm that computes a succinct description of \(C\) given \(n\). For linear codes, such a succinct description could be a generator matrix or a parity check matrix.

Let \(q\ge 2\) and \(0\le p\le 1-\tfrac 1q\). The \(q\)-ary Symmetric Channel with crossover probability \(p\), denoted \(q\mathrm{SC}_p\), is the stochastic channel with \(\mathcal{X}=\mathcal{Y}=[q]\) and transition matrix

That is, every symbol is retained with probability \(1-p\) and distorted to each of the \(q-1\) other symbols with equal probability \(\tfrac {p}{q-1}\).

A (memoryless) stochastic channel consists of a finite input alphabet \(\mathcal{X}\), a finite output alphabet \(\mathcal{Y}\), and a transition matrix \(\mathbf{M}\) indexed by \(\mathcal{X}\times \mathcal{Y}\), where for every \((x,y)\in \mathcal{X}\times \mathcal{Y}\), \(\mathbf{M}(x,y)=\Pr (y\mid x)\) denotes the probability that \(y\) is output by the channel when \(x\) is input to the channel; in particular \(\sum _{y\in \mathcal{Y}}\mathbf{M}(x,y)=1\) for every \(x\in \mathcal{X}\). The channel is memoryless in the sense that the noise acts independently on each symbol of a transmitted string.

A linear \([n,k]\) code \(C\) is called strongly explicit if, given any index pair \((i,j)\in [k]\times [n]\), there is a \(\mathrm{poly}(\log n)\)-time algorithm that outputs \(G_{i,j}\), where \(G\) is a generator matrix of \(C\).

Given a code \(C\), a fixed codeword \(\mathbf{c} \in C\), and an error pattern \(\mathbf{e}\) such that some codeword of \(C\) lies within Hamming distance \(\rho n\) of \(\mathbf{c} + \mathbf{e}\), the error pattern \(\mathbf{e}\) is associated with a codeword \(c(\mathbf{e})\), namely the closest codeword of \(C\) that lies within Hamming distance \(\rho n\) from \(\mathbf{c} + \mathbf{e}\).

The list-decoding capacity (of the \(q\)-ary worst-case error channel), as a function of the fraction of errors \(\rho \), is \(1 - H_q(\rho )\).

Given \(0 \leq \rho \leq 1\) and \(L \geq 1\), a code \(C \subseteq \Sigma ^n\) is \((\rho , L)\)-list decodable if for every received word \(\mathbf{y} \in \Sigma ^n\),

A list-decoding algorithm for \(C\), given an error parameter \(\rho \), a received word \(\mathbf{y}\), is required to output all codewords of \(C\) within relative Hamming distance \(\rho \) of \(\mathbf{y}\); in particular, if the fraction of errors that occurred is at most \(\rho \), the transmitted codeword is guaranteed to appear in the output list. If \(C\) is \((\rho , L)\)-list decodable then any such algorithm outputs at most \(L\) codewords. The list-decodability of an infinite family of codes \(\mathscr {C}\) (with polynomial-sized lists) is the limit of \(\rho \) over all polynomials \(L\) such that all sufficiently long codes \(C \in \mathscr {C}\) are \((\rho , L)\)-list decodable.

By Corollary 175, the tightest upper bound on \(A(n,d)\) (the largest size of a binary code of length \(n\) and distance \(d\)) obtainable by this method is the optimum value of the following optimization problem, which is the dual of the linear program of Definition 170:

Given nonnegative reals \(\beta _1,\dots ,\beta _n\), set \(\beta _0 = 1\) and define the degree-\(n\) polynomial (in the Krawtchouk basis of Proposition 168)

Fix a block length \(n\). For \(\ell = 0,1,\dots ,n\), the Krawtchouk polynomial \(K_\ell (X)\) is the real polynomial

where \(\binom {X}{j}\) denotes the polynomial \(X(X-1)\cdots (X-j+1)/j!\) (so that plugging in \(X = m\) for an integer \(m\) recovers the usual binomial coefficient \(\binom {m}{j}\)), and similarly for \(\binom {n-X}{\ell -j}\). The Krawtchouk function \(K_\ell (i)\), for \(i = 0,1,\dots ,n\), is the evaluation of \(K_\ell (X)\) at \(X = i\).

Fix a block length \(n\) and a target distance \(d\). Consider the linear program in real variables \(A_0,\dots ,A_n\):

We write \(\mathrm{LP}(n,d)\) for the optimum value of this program. (For a linear code \(C\) of distance \(d\), the intended meaning of \(A_i\) is the number of weight-\(i\) codewords of \(C\); the first three families of constraints are then immediate, while the last family follows from the MacWilliams identities relating the weight distribution of \(C\) to that of its dual code. )

For a (not necessarily linear) binary code \(C\) and \(i = 0,1,\dots ,n\), define

the normalized distance distribution function of \(C\).

It is convenient to switch back and forth between multivariate functions and multivariate polynomials. For \(f : \mathbb {F}_q^m \to \mathbb {F}_q\), let \(\deg (f)\) be the minimal total degree of a polynomial \(P \in \mathbb {F}_q[X_1,\ldots ,X_m]\) (where \(\mathbb {F}_q[X_1,\ldots ,X_m]\) denotes the set of all \(m\)-variate polynomials with coefficients from \(\mathbb {F}_q\)) such that \(f(\alpha ) = P(\alpha )\) for every \(\alpha \in \mathbb {F}_q^m\). Since \(a^q - a = 0\) for every \(a \in \mathbb {F}_q\) (Lemma 180), it follows that a minimal-degree polynomial representing \(f\) does not contain, in any single variable, a monomial of degree more than \(q-1\). Similarly \(\deg _{X_i}(f)\) denotes the degree of (the minimal polynomial corresponding to) \(f\) in variable \(X_i\). In this notation, for every \(f : \mathbb {F}_q^m \to \mathbb {F}_q\) we have \(\deg _{X_i}(f) \leq q-1\) for every \(i \in [m]\).

For a polynomial \(p \in \mathbb {F}_q[X_1,\ldots ,X_m]\) and \(i \in [m]\), \(\deg _{X_i}(p)\) denotes the degree of \(p\) in the variable \(X_i\), i.e. the maximum \(d_i\) appearing in a monomial of \(p\) with nonzero coefficient.

Reed-Muller codes are given by three parameters: a prime power \(q\) and positive integers \(m\) and \(r\) and consist of the evaluations of \(m\)-variate polynomials of degree at most \(r\) over all of the domain \(\mathbb {F}_q^m\). The Reed-Muller code with parameters \(q,m,r\), denoted \(\mathrm{RM}(q,m,r)\), is the set of evaluations of all \(m\)-variate polynomials in \(\mathbb {F}_q[X_1,\ldots ,X_m]\) of total degree at most \(r\) and individual degree at most \(q-1\) over all points in \(\mathbb {F}_q^m\). Formally

The Reed-Muller code with parameters \((q,m,r)\) clearly has alphabet \(\mathbb {F}_q\) and block length \(n = q^m\). It can be verified that \(\mathrm{RM}(q,m,r)\) is a linear code (Exercise 9.1).

For integers \(q,m,r\) let

and let \(K_{q,m,r} = |S_{q,m,r}|\).

For a monomial \(\mathbf{X}^{\mathbf{d}} = X_1^{d_1} \cdot X_2^{d_2} \cdots X_m^{d_m}\) its total degree is \(d_1 + d_2 + \cdots + d_m\). The total degree of a polynomial \(P(\mathbf{X}) = \sum _{\mathbf{d}} c_{\mathbf{d}} \mathbf{X}^{\mathbf{d}}\) over \(\mathbb {F}_q\) (i.e. every \(c_{\mathbf{d}} \in \mathbb {F}_q\)) is the maximum, over \(\mathbf{d}\) such that \(c_{\mathbf{d}} \neq 0\), of the total degree of \(\mathbf{X}^{\mathbf{d}}\). We denote the total degree of \(P\) by \(\deg (P)\).

Fix \(q \ge 2\), \(k \ge 1\) and \(Q = q^k\). Consider two codes, called the outer code and inner code:

Since the alphabet size of \(C_{out}\) equals \(Q = q^k\), the number of possible messages of \(C_{in}\), we may fix a bijection between \([Q]\) and \([q]^k\) and thereby use \(C_{in}\) to encode any single symbol of a codeword of \(C_{out}\). The concatenated code \(C_{out}\circ C_{in} : [q]^{kK} \to [q]^{nN}\) is then defined, for \(\mathbf{m} = (m_1,\ldots ,m_K) \in [Q]^K\), by

where \(C_{out}(\mathbf{m}) = (C_{out}(\mathbf{m})_1,\ldots , C_{out}(\mathbf{m})_N)\). (Unlike string concatenation, this is a recursive construction: the outer code is used to reduce the block length we need from the inner code.)

Fix a prime power \(q\), a positive integer \(k\), and \(0{\lt}R{\lt}1\). Let \(C_{out}\) be the \([N,K]_{q^k}\) Reed–Solomon code (Definition 128) of rate \(R\), evaluated over \(\mathbb {F}_{q^k}^*\), where \(N = q^k-1\); it has relative distance \(\delta _{out} = 1-R\). Let \(\{ C_{in}^\alpha \} _{\alpha \in \mathbb {F}_{q^k}^*}\) be the Wozencraft ensemble of Definition 207, and write \(C_{in}^1,\ldots , C_{in}^N\) for its \(N\) codes in some fixed order matching the \(N\) coordinates of \(C_{out}\). The Justesen code is the concatenated code

defined, for a message \(\mathbf{m}\in (\mathbb {F}_{q^k})^K\) with \((c_1,\ldots ,c_N)=C_{out}(\mathbf{m})\), by \(C^*(\mathbf{m}) = \big(C_{in}^1(c_1),\ldots ,C_{in}^N(c_N)\big)\). Since each \(C_{in}^i\) has rate \(\tfrac 12\), \(C^*\) has rate \(\tfrac {R}{2}\).

Fix a prime power \(q\) and a positive integer \(k\), and let \(N = q^k - 1\). For \(\alpha \in \mathbb {F}_{q^k}^*\), define the inner code \(C_{in}^\alpha : \mathbb {F}_q^k \to \mathbb {F}_q^{2k}\) by

where \(x\) and \(\alpha x\) are elements of \(\mathbb {F}_{q^k}\), viewed as vectors in \(\mathbb {F}_q^k\) via the standard identification. The Wozencraft ensemble is the collection of codes \(\{ C_{in}^\alpha \} _{ \alpha \in \mathbb {F}_{q^k}^*}\), indexed by the \(N\) elements of \(\mathbb {F}_{q^k}^*\).

Given a bipartite graph \(G = (L,R,E)\), its adjacency matrix, denoted \(A_G\), is an \(|R| \times |L|\) binary matrix, where we index each row by an element of \(R\) and every column by an element of \(L\) such that for every \((r,\ell ) \in R \times L\), the \((r,\ell )\)’th entry of \(A_G\) is \(1\) if \((\ell ,r) \in E\) and \(0\) otherwise. Conversely, every matrix \(A \in \{ 0,1\} ^{n \times m}\) corresponds to a bipartite graph \(G_H = (L,R,E)\) with \(|L| = m\) and \(|R| = n\) with \((i,j) \in E\) if and only if \(A_{ij} = 1\).

A bipartite graph is a triple \(G = (L,R,E)\), where \(L\) is the set of ‘left’ vertices, \(R\) is the set of ‘right’ vertices, and \(E \subseteq L \times R\) is the set of edges. (A bipartite graph \((L,R,E)\) is a special case of a graph \((V = L \cup R, E)\).)

For integers \(k,n,b\) and \(B\), codes \(C_{\text{out}} : \mathbb {F}_q^k \to (\mathbb {F}_q^b)^n\) and \(C_{\text{in}} : \mathbb {F}_q^b \to \mathbb {F}_q^B\), and a \(B\)-regular ordered bipartite graph \(G = (L,R,E)\) with \(|L|=|R|=n\), the \(C_{\text{in}}\)-coded-\(G\)-amplification of \(C_{\text{out}}\) is the code \(\mathscr {CA}(C_{\text{out}},C_{\text{in}},G) : \mathbb {F}_q^k \to (\mathbb {F}_q^B)^n\) given by \(\mathscr {CA}(C_{\text{out}},C_{\text{in}},G)(\mathbf{u}) = G_{\mathrm{mix}}\big((C_{\text{out}}\circ C_{\text{in}})(\mathbf{u})\big)\), where \(C_{\text{out}}\circ C_{\text{in}} : \mathbb {F}_q^k \to (\mathbb {F}_q^B)^n\) denotes the encoding of the concatenation of the codes \(C_{\text{out}}\) and \(C_{\text{in}}\). Specifically, for \(\mathbf{u} \in \mathbb {F}_q^k\) we have \((C_{\text{out}}\circ C_{\text{in}})(\mathbf{u}) = (w_1,\ldots ,w_n)\) where \(w_i = C_{\text{in}}(v_i)\) and \((v_1,\ldots ,v_n) = C_{\text{out}}(\mathbf{u})\).

A bipartite graph \(G = (L,R,E)\) is said to be a \((\gamma ,\varepsilon )\)-disperser if for all subsets \(S \subseteq L\) with \(|S| \ge \gamma n\), we have \(|N(S)| \ge (1-\varepsilon )m\).

Let \(G = (L,R,E)\) be a \(c\)-left-regular and \(d\)-right-regular ordered bipartite graph with \(L=[n]\), \(R=[m]\), and let \((N_1(j),\ldots ,N_d(j)) \in [n]^d\) denote the ordered neighborhood of \(j \in [m]\). Let \(\Sigma = \{ 0,1\} ^d\). For \(\mathbf{w} \in \{ 0,1\} ^n\), define \(G(\mathbf{w}) \in \Sigma ^m\) by

Let \(C\) be a binary linear code of block length \(n = |L|\). Now define the code \(G(C)\) as

We refer to \(G(C)\) as the \(G\)-amplification of \(C\).

The Double Cover of a graph \(X = (V_X,E_X)\) is defined as the bipartite graph \(G' = (L_{G'},R_{G'},E_{G'})\) with vertices \(L_{G'} = \{ u' \mid u \in V_X\} \) and \(R_{G'} = \{ u'' \mid u \in V_X\} \), and edges \(E_{G'} = \{ (u',v''),(v',u'') \mid (u,v) \in E_X\} \).

Given an undirected graph \(X = (V,E)\) and sets \(A,B \subseteq V\), we define \(E(A,B)\) to be the set of pairs \((a,b)\) with \(a \in A\) and \(b \in B\) such that \((a,b) \in E\). I.e., \(E(A,B) = \{ (a,b) \in A \times B \mid (a,b) \in E\} \). (Note that if \(a,b \in A \cap B\) then both \((a,b)\) and \((b,a)\) belong to \(E(A,B)\).)

The Edge Vertex Incidence Graph of a graph \(G' = (V,E)\) is defined as the bipartite graph \(G = (L,R,E')\) where \(L = E\), \(R = V\) and \(E' = \{ (e,v) \mid v \in e \in E\} \).

Let \(\mathbf{M} \in \mathbb {R}^{n \times n}\) be a matrix over the reals. Then \(\lambda _i\) is an eigenvalue of \(\mathbf{M}\) if there exists a vector \(\mathbf{v}_i \in \mathbb {R}^n\), \(\mathbf{v}_i \ne 0\), such that \(\mathbf{M}\cdot \mathbf{v}_i = \lambda _i \cdot \mathbf{v}_i\).

A code \(C \subseteq \mathbb {F}_2^n\) is called an expander code if there is a bipartite expander graph \(G\) such that \(C = C(G)\). If \(G\) is \(d\)-right bounded then \(C(G)\) is said to be a \(d\)-LDPC (for Low Density Parity Check) Code.

An \((n,m,c,\gamma ,\alpha )\) bipartite expander is a \(c\)-left regular bipartite graph \(G = (L,R,E)\) where \(|L| = n\) and \(|R| = m\) such that for every \(S \subseteq L\) with \(|S| \le \gamma n\), we have

An infinite family of bipartite graphs \(\{ G_i\} _{i \in \mathbb {Z}_+}\) is termed a \((c,\gamma ,\alpha )\)-bipartite expander family if for every \(i \in \mathbb {Z}_+\), \(G_i\) is an \((n_i,m_i,c,\gamma ,\alpha )\) expander for some \(n_i,m_i \in \mathbb {Z}_+\). We say \(\{ G_i\} _{i \in \mathbb {Z}_+}\) is a bipartite expander family if there exist \(c \in \mathbb {Z}_+\) and \(\alpha ,\gamma {\gt} 0\) such that \(\{ G_i\} _{i \in \mathbb {Z}_+}\) is a \((c,\gamma ,\alpha )\)-bipartite expander family.

Given any \([n,k]_2\) code \(C\) with parity check matrix \(H\), we will call the bipartite graph \(G_H\) with \(A_{G_H} = H\) a factor graph of \(C\). Further, given a bipartite graph \(G = (L,R,E)\) with \(|L| \ge |R|\), we will denote the corresponding code with parity check matrix \(A_G\) to be \(C(G)\).

Given an ordered \(c\)-left regular \(d\)-right regular graph \(G=(L,R,E)\) with \(L=[n]\) and \(R=[m]\), the \(G\)-mixing operator is a function \(G_{\mathrm{mix}} : \Gamma ^n \to \Sigma ^m\) where \(\Gamma = \mathbb {F}_q^c\) and \(\Sigma = \mathbb {F}_q^d\) given as follows: for \(\mathbf{u} = (u_1,\ldots ,u_n) \in \Gamma ^n\) with \(u_i = (u_i(1),\ldots ,u_i(c))\), we have \(G_{\mathrm{mix}}(\mathbf{u}) = \mathbf{v} = (v_1,\ldots ,v_m) \in \Sigma ^m\) where \(v_j = (v_j(1),\ldots ,v_j(d))\) is given by \(v_j(b) = u_i(a)\) if \((i,j) \in E\) and \(j\) is the \(a\)th neighbor of \(i\) and \(i\) is the \(b\)th neighbor of \(j\). That is, the \(a\)th symbol of \(u_i\) is ‘sent’ to the \(b\)th symbol of \(v_j\) via the edge \((i,j)\).

For a left vertex set \(S \subseteq L\), a vertex \(u \in R\) is called a neighbor of \(S\) if it is adjacent to some vertex in \(S\). We denote by \(N(S)\) the set of neighbors of \(S\). We analogously define \(N(T)\) for any \(T \subseteq R\).

A graph \(G = (V,E)\) is said to be \(c\)-bounded if every vertex has degree at most \(c\). It is said to be \(c\)-regular if every vertex has degree exactly \(c\). Similarly, a bipartite graph \(G = (L,R,E)\) is said to be \(c\)-left regular (bounded) if every vertex in \(L\) has degree exactly (resp., at most) \(c\). It is said to be \(d\)-right regular (bounded) if every vertex in \(R\) has degree exactly (resp., at most) \(d\).

A graph \(X = (V,E)\) is said to be an \((n,d,\lambda )\)-spectral expander if \(X\) is a \(d\)-regular (not necessarily bipartite) graph on \(n\) vertices and \(\lambda \ge \max \{ |\lambda _2|,|\lambda _n|\} \), where \(\lambda _1 \ge \lambda _2 \ge \cdots \ge \lambda _n\) are the eigenvalues of the adjacency matrix of \(X\).

For a positive integer \(d\) and \(0 \le \lambda {\lt} d\), we say that an infinite family of graphs \(\{ X_n\} _{n\in \mathbb {Z}_+}\) with \(X_n\) having \(n\) vertices and being \(d\)-regular, is a \((d,\lambda )\)-spectral expander family if \(\lambda (X_n) \le \lambda \) for every \(n\). We refer to a family as a spectral expander family if there exists \(\lambda {\lt} d\) such that the family is a \((d,\lambda )\)-spectral expander family.

Given a \(d\)-right regular bipartite graph \(G=(L,R,E)\) with \(L=[n]\) and \(|R|=m\) and a binary linear code \(C_0 \subseteq \mathbb {F}_2^d\), the Tanner code \(X(G,C_0)\) is defined as the set

Given a bipartite graph \(G = (L,R,E)\) and a left vertex set \(S \subseteq L\), a vertex \(u \in R\) is called a unique neighbor of \(S\) if it is adjacent to exactly one vertex in \(S\). We let \(U(S)\) denote the set of unique neighbors of \(S\).

For a bivariate polynomial \(Q(X,Y) = \sum _{i,j} c_{ij} X^i Y^j\), \(\deg _X(Q)\) is the maximum degree of \(X\) appearing in any monomial of \(Q(X,Y)\) with nonzero coefficient, and similarly \(\deg _Y(Q)\) is the maximum degree of \(Y\). If \(\deg _X(Q) \le a\) and \(\deg _Y(Q) \le b\) then \(Q(X,Y) = \sum _{0 \le i \le a, 0 \le j \le b} c_{ij}X^iY^j\) has \((a+1)(b+1)\) coefficients.

Given a received word \(y=(y_1,\dots ,y_n)\) and a polynomial \(P(X)\), a non-zero polynomial \(E(X)\) is called an error-locator polynomial for \((P,y)\) if for all \(i \in [n]\),

In particular, the polynomial \(E(X) = \prod _{i : y_i \neq P(\alpha _i)} (X-\alpha _i)\) is an error-locator polynomial of degree exactly \(e := |\{ i \mid y_i \neq P(\alpha _i)\} |\), and for every \(1 \le i \le n\) it satisfies \(y_i E(\alpha _i) = P(\alpha _i)E(\alpha _i)\).

Let

A bivariate polynomial \(\)Q(X,Y)\( has \)\(\)r\( roots at \)(0,0)\(\) if \(\)Q(X,Y)\( has no non-zero monomial of degree at most \)r-1\( (i.e.\ every monomial \)X^iY^j\( with \)c_i,j ≠0\( satisfies \)i+j ≥r\(). \)

\(\)Q(X,Y)\( has \)\(\)r\( roots at \)(α,β)\(\) if the shifted polynomial \(\)Q_α,β(X,Y) := Q(X+α,Y+β)\( has \)r\( roots at \)(0,0)\( (Definition~ \ref{def:c12-multiplicity-origin}). \)

• Input: Code parameters \(\mathbb {F}_q\), \((\alpha _1,\dots ,\alpha _n) \in \mathbb {F}_q^n\), \(k\) and \(e\). Received word \(y=(y_1,\dots ,y_n) \in \mathbb {F}_q^n\).

• Output: The set of all polynomials \(P(X) \in \mathbb {F}_q[X]\) of degree less than \(k\) such that \(t := |\{ i \in [n] \mid y_i = P(\alpha _i)\} | \ge n-e\).

• Input: Code parameters \(\mathbb {F}_q\), \((\alpha _1,\dots ,\alpha _n) \in \mathbb {F}_q^n\) and \(k\). Received word \(y \in \mathbb {F}_q^n\).

• Output: A polynomial \(P(X) \in \mathbb {F}_q[X]\) of degree less than \(k\) such that \(e := |\{ i \in [n] \mid y_i \neq P(\alpha _i)\} | {\lt} \frac{n-k+1}{2}\), if such a polynomial exists, and fail otherwise.

In the soft decoding problem, the decoder is given non-negative weights

The \((1,w)\)-weighted degree of the monomial \(X^iY^j\) is \(i+wj\). The \((1,w)\)-weighted degree of \(Q(X,Y)\) (or just its \((1,w)\)-degree) is the maximum \((1,w)\)-weighted degree over its monomials with non-zero coefficient. (The \((1,1)\)-degree is the usual total degree.) A bivariate polynomial of \((1,w)\)-degree at most \(D\) can be written \(Q(X,Y) = \sum _{i+wj \le D,\, i,j \ge 0} c_{i,j}X^iY^j\).

A one-dimensional \(\)s\(-variate affine form\) \(\)a F_q[Z_1,…,Z_s]\( is a polynomial of the form \)a(Z_1,…,Z_s) = ∑_i=1^s α_i Z_i + α_0\(, i.e.\ a polynomial of degree at most \)1\(. An \)\(\)m\(-dimensional \)s\(-variate affine form\) \(\)A = a_1,…,a_m\( is simply an \)m\(-tuple of one-dimensional affine forms. \)

Given an

For a prime power

A function \(\)Φ: F_q^m F_q^m\( is said to be an \)\(\)F_q\(-linear bijection\) if

\(\)Φ\( is a bijection, i.e.\ \)Φ(u)=Φ(v) ⇒u=v\( for every \)u,vF_q^m\(; and \item \)Φ\( is \)F_q\(-linear, i.e.\ for every \)α,βF_q\( and \)u,vF_q^m\(, \)Φ(αu+βv) = αΦ(u)+βΦ(v)\(. \)

For

For an integer \(\)d\(, let \)d_0,d_1,d_2,…\( denote its expansion in base \)q\(, i.e.\ \)d = ∑_i=0^∞d_iq^i\( with \)0≤d_i<q\( for every \)i\(. For a monomial \)Z^d\(, define its \)\(\)q\(-degree\), denoted \(\)_q(Z^d)\(, to be \)∑_i=0^∞d_i\(. For a polynomial \)p(Z) = ∑_d c_dZ^d\(, define its \)q\(-degree, \)_q(p)\(, to be \)_d∣c_d≠0{_q(Z^d)}\(. \)

For

For

Given

We define the

For jointly distributed random variables

For a discrete random variable

A pair \(\)(i,i’)\( are \)\(\)j\(th-level siblings\) if they are in the same block at the \(\)j\(th level and \)i’=i+2^t-j\(. For \)i[n=2^t]\( and \)0≤j≤t\(, let \[ S_{i,j} \stackrel{\text{def}}{=} \{ k\in [n]\mid i\equiv k\! \! \pmod{2^{t-j}}\} . \] \)

\(\)P_n(Z) = (Z_1^(t),…,Z_n^(t))\(. \)

\(\)t\( (i.e., on \)n=2^t\(). For \)t=0\( (\)n=1\(), \)P_1(Z)=Z=(Z_1^(0))\( trivially. For \)t≥1\(, write \)Z=(U,V)\( with \)U=(Z_1,…,Z_n/2)\(, \)V=(Z_n/2+1,…,Z_n)\(; by Definition~ \ref{def:c16-basic-polarizing-matrix}, \)P_n(Z)=(P_n/2(U+V),P_n/2(V))\(. By definition, for \)i≤n/2\(, \)Z_i^(1)=Z_i+Z_i+n/2=U_i+V_i\(, i.e., the first block at level \)1\( consists of \)U+V\(; for \)i>n/2\(, \)Z_i^(1)=V_i-n/2\( carries \)V\( unchanged. Applying the inductive hypothesis (for \)t-1\() to \)U+V\( gives \)P_n/2(U+V)=((U+V)_1^(t-1),…,(U+V)_n/2^(t-1))\(, and since level-\)j\( variables (\)j≥1\() for indices \)≤n/2\( are computed entirely from \)Z^(1)|_{1,…,n/2}=U+V\( by the same recursive rule shifted by one level, \)(U+V)_i^(t-1)=Z_i^(t)\( for \)i≤n/2\(. Symmetrically, \)P_n/2(V)_i=Z_n/2+i^(t)\( for \)i≤n/2\(. Combining, \)P_n(Z)=(Z_1^(t),…,Z_n^(t))\(. \)

\(\)X_0,…,X_j,…\( with \)X_j[0,1]\( is \emph{locally polarizing} if: \begin{enumerate} \item \textbf{(Unbiased)} For every \end{enumerate}\)j\( and \)a[0,1]\(: \)E[X_j+1∣X_j=a]=a\(. \item \textbf{(Variance in the middle)} For every \)τ>0\( there exists \)θ=θ(τ)>0\( such that for all \)j\(: if \)X_j(τ,1-τ)\( then \)|X_j+1-X_j|≥θ\(. \item \textbf{(Suction at the ends)} For every \)c<∞\( there exists \)τ=τ(c)>0\( such that (i) if \)X_j≤τ\( then \)[X_j+1≤X_j/c]≥1/2\(; and (ii) if \)1-X_j≤τ\( then \)[1-X_j+1≤(1-X_j)/c]≥1/2\(. \)

The sequence is simple if for every sequence \(\)a_0,…,a_j\(, conditioned on \)X_0=a_0,…,X_j=a_j\(, there are two values \)a^+,a^ℓ\( such that \)X_j+1\( equals \)a^+\( with probability \)1/2\( and \)a^ℓ\( with probability \)1/2\(. \)

For \(\)n≥m\(, a pair \)(H,D)\( with \)HF_2^n×m\( and \)D:F_2^mF_2^n\( forms a \)\(\)τ\(-error linear compression scheme\) for \(\)Bern(p)^n\( if \)H\( has rank \)m\( and \[ \Pr _{\mathbf{Z}\sim \mathrm{Bern}(p)^n}[D(\mathbf{Z}\cdot \mathbf{H})\ne \mathbf{Z}]\le \tau . \] The ratio \)m/n\( is called the \emph{(compression) rate} of the scheme. \)

A sequence of random variables

An invertible matrix

A sequence of random variables

The

For \(\)k=2^t\( we define codes \)C_k : F_2^k F_2^3k\( inductively, with \)|C_k(x)| = 4k\( (i.e. rate \)1/4\(). \emph{Base case.} There is a constant \)k_0\( such that for all \)k ≤k_0\(, \)C_k\( is chosen to be the check bits of an arbitrary systematic code of rate \)1/4\( (of the fixed constant length \)4k\(). \emph{Inductive step.} Assume \)C_k/2\( has been defined. For \)x F_2^k\(, define \[ C_k(\mathbf{x}) = (\mathbf{y}_1,\mathbf{y}_2,\mathbf{y}_3), \qquad \mathbf{y}_1 = R_k(\mathbf{x}), \quad \mathbf{y}_2 = C_{k/2}(\mathbf{y}_1), \quad \mathbf{y}_3 = R_{2k}(\mathbf{y}_1,\mathbf{y}_2). \] (Here \)y_1 F_2^k/2\(, \)y_2 F_2^3k/2\(, so \)(y_1,y_2) F_2^2k\( is a valid input to \)R_2k\(, and \)y_3 F_2^k\(; thus \)|C_k(x)| = k/2+3k/2+k = 3k\(.) The final systematic code is \)C_k(x) = (x, C_k(x))\(. \)

Given the graph \(\)B_k = ([k],[k/2],E)\( of Construction~ \ref{constr:c18-Bk}, define the \emph{error-reduction code} \)R_k : F_2^k F_2^k/2\( by \[ R_k(\mathbf{x}) = \mathbf{y}, \qquad y_j = \bigoplus _{i \in N(j)} x_i \quad \text{for } j \in [k/2], \] where \)N(j)\( denotes the neighborhood of right vertex \)j\( in \)B_k\(. The associated systematic encoding is \)R_k(x) = (x, R_k(x))\(. This is a code of rate \)2/3\(, mapping \)k\( message bits to \)3k/2\( codeword bits, of which the first \)k\( are the message bits and the remaining \)k/2\( are check bits. \)

A linear code

Consider a linear code

A hash family

Given a hash family

Given

Given a domain

Given a string

For any integer

A fingerprint (image / sensor reading) is stored as a collection of triples, called minutiae. Each minutia is located where a ridge of the fingerprint splits into two, or where a ridge ends. The

Let

A data stream algorithm is an algorithm satisfying the following four requirements.

1. The algorithm makes one sequential pass over the input.

2. The algorithm uses poly-log space (in particular, it cannot store the entire input).

3. The algorithm has poly-log update time, i.e. whenever a new item appears, the algorithm updates its internal state in poly-log time.

4. The algorithm has poly-log reporting time, i.e. at any point of time the algorithm can return the required answers in poly-log time.

A \(\)t ×N\( matrix \)M\( is \)\(\)d\(-disjunct\) if and only if for every \(\)S ⊂[N]\( with \)|S| ≤d\( and for every \)j S\(, there exists \)i [t]\( such that \)M_ij = 1\( but \)M_ik = 0\( for all \)k S\(. Or, equivalently, \[ M^j \not\subseteq \bigcup _{k \in S} M^k. \] \)

Given a stream of pairs

Given

A \(\)t ×N\( matrix \)M\( is \)\(\)d\(-separable\) if and only if for every \(\)S_1 ≠S_2 ⊆[N]\( such that \)|S_1|,|S_2| ≤d\(, we have \[ \bigcup _{j \in S_1} M^j \ne \bigcup _{i \in S_2} M^i. \] \)

Given a subset of \(\)N\( items with \)d\( defects represented as \)x {0,1}^N\( with \)wt(x) ≤d\(, the minimum number of \emph{non-adaptive} tests that one would have to make (over all valid non-adaptive schemes that correctly determine \)x\() is defined as \)t(d,N)\(. \)

Given a set of \(\)N\( items with \)d\( defects, \)t^a(d,N)\( is defined as the minimum number of \emph{adaptive} tests that one would have to make to detect all the defective items. \)

Given

For

A group testing scheme is adaptive if each test may be chosen based on the outcomes of all previously performed tests. A group testing scheme is non-adaptive if the entire collection of tests is fixed in advance, before any test outcome is observed.

For a real number

For a matrix

Let

For a real number

The Maximum Cut Problem is the following decision problem.

• Input: a graph

The Nearest Codeword Problem is the following decision problem.

• Input:

Fix a family of codes \(\){C_n}_n\( given by generator matrices \){G_n}_n\(, with \)G_nF^k(n)×n\(. The problem \)NCPP{G_n}_n\( is the following decision problem. \begin{itemize} \item \textbf{Input}: \end{itemize}\)(v,t)\( where \)vF^n\( and \)tZ^≥0\(. \item \textbf{Output}: \textsc{Yes} if there exists \)xF^k(n)\( such that \)Δ(v,xG_n)≤t\(, and \textsc{No} otherwise. \)

A non-uniform algorithmic solution to \(\)NCPP{G_n}_n\( consists of an algorithm \)A(·,·;·)\( together with a sequence of advice strings \){B_n}_n\( such that \)A(v,t;B_n)\( correctly solves \)NCPP{G_n}_n\( for every \)(v,t)\( with \)vF^n\(, subject to: \begin{enumerate} \item \end{enumerate}\)A\( runs in time polynomial in \)n\( (in particular \)B_n\( has length polynomial in \)n\(); \item the time needed to \emph{compute} \)B_n\( from \)G_n\( may be unboundedly large. \)

For a positive integer \(\)t\( and real \)δ≥0\(, a generator \)G : F_2^s F_2^n\( is a \)\(\)δ\(-almost \)t\(-wise independent generator\) if for every subset \(\)T⊆[n]\( with \)|T|=t\(, \)G|_T(z)\( is \)δ\(-close (in total variation distance) to being uniformly distributed over \){0,1}^t\( when \)z\( is distributed uniformly over \){0,1}^s\(. \)

For

Given a function

The communication complexity of a protocol

The communication complexity of a randomized protocol

A (deterministic) protocol

1. A function

A function

We say that a linear code \(\)C ⊆F_2^N\( is \)\(\)ε\(-balanced\) if for every pair of distinct codewords \(\)x,yC\( we have \[ \left(\frac{1}{2}-\varepsilon \right)N \le \Delta (\mathbf{x},\mathbf{y}) \le \left(\frac{1}{2}+\varepsilon \right)N. \] \)

We say that a generator \(\)G : F_2^s F_2^n\( is \)\(\)ε\(-biased\) if for every non-zero linear function \(\)ℓ: F_2^n F_2\( we have \[ \Big|\Pr _{z\in \mathbb {F}_2^s}\big[\ell (G(z))=1\big] - \tfrac {1}{2}\Big| \le \varepsilon . \] \)

Given an algorithm \(\)A\(, input \)x\(, and parameter \)ε[0,1]\(, we say that a generator \)G : {0,1}^s {0,1}^m\( \)\(\)ε\(-fools the pair \)(A,x)\(\) if

where \(\)f\( is the function \)A\( is meant to compute. \)

Given an algorithm

For every

For

For a positive integer \(\)t\(, a \)\(\)t\(-clause\) over Boolean variables \(\)x_1,…,x_n\( is a disjunction \)C = ℓ_1 ∨∨ℓ_t\( of \)t\( distinct literals (a literal being a variable or its negation), which is true under an assignment \)a{0,1}^n\( if and only if at least one of \)ℓ_1,…,ℓ_t\( evaluates to true under \)a\(. Given a collection \)Φ= (C_1,…,C_m)\( of \)m\( \)t\(-clauses over \)x_1,…,x_n\( and an assignment \)a{0,1}^n\(, let \)val(Φ,a)\( denote the fraction of clauses of \)Φ\( satisfied by \)a\(, and let \)opt(Φ) = _a{val(Φ,a)}\(. The \textsc{Max $t$-SAT} problem asks: given such a \)Φ\(, find an assignment \)a{0,1}^n\( with \)val(Φ,a) = opt(Φ)\(. \)

A protocol

A permutation

We say that a function \(\)F : {0,1}^k+ℓ {0,1}^k+ℓ\( is an \)\(\)ℓ\(-padding\) (or simply padding) of \(\)f : {0,1}^k {0,1}^k\( if for every \)x{0,1}^k\( and \)i{0,1}^ℓ\( we have \)F(x,i) = (f(x),i)\(. \)

For a field

We say that

A (deterministic) protocol

A randomized protocol

We say a randomized protocol

Given a generator \(\)G : {0,1}^s {0,1}^n\( and \)T ⊆[n]\(, let \)G|_T(·)\( denote the projection of \)G(·)\( to the coordinates of \)T\(. We say \)G\( is a \)\(\)t\(-wise independent generator\) if for every subset \(\)T⊆[n]\( with \)|T|=t\(, \)G|_T(z)\( is uniformly distributed over \){0,1}^t\( when \)z\( is distributed uniformly over \){0,1}^s\(. \)

The variation distance between two distributions

For every real numbers

For all integers

For all integers

For any vectors

For

For every real \(\)x > 0\(, \[ \left(1 + \frac{1}{x}\right)^x \leq e. \] \)

For

For

Let

For

For every integer

Let

Let

Let

Let

Algorithm 588 outputs the correct answer with probability at least

Algorithm 594 runs in time

Construction 598, together with the map \(\)S = {i V : x_i = 1}\( from solutions of the produced \)MaxLinearEq\( instance to subsets of \)V\(, is a valid polynomial-time reduction from \)MaxCut(k,n,s)\( to \)MaxLinearEq(k,n,s)\(: it runs in polynomial time, and a solution \)(x_1,…,x_k)\( satisfies the equation \)x_i + x_j = 1\( (associated to edge \)(i,j)\() if and only if exactly one of \)i,j\( lies in \)S\(, i.e. if and only if \)(i,j)\( is a cut edge for \)S\(. Consequently \)(x_1,…,x_k)\( satisfies at least \)s\( equations if and only if \)S\( is a cut of size at least \)s\(. \)

If \(\)L_1 ≤_P L_2\( and \)L_2 P\(, then \)L_1 P\(. \)

Let

Let

Let

If

Let

Let

Root-Find

A polynomial

Let

If

For random variables

If

For any \(\mathbf u,\mathbf v \in \{ 0,1\} ^n\), where \(\mathbf u + \mathbf v\) denotes coordinatewise XOR,

For any binary linear code \(C\) (not necessarily distinct) messages \(\mathbf x,\mathbf y\), \(C(\mathbf x) + C(\mathbf y) = C(\mathbf x + \mathbf y)\) (coordinatewise XOR throughout).

Given a matrix \(G\) of dimension \(k\times n\) that is a generator matrix of subspace \(S_1\), and a matrix \(H\) of dimension \((n-k)\times n\) that is a parity check matrix of subspace \(S_2\), such that \(G H^T = \mathbf{0}\), then \(S_1 = S_2\).

Algorithm 64 correctly outputs \(\mathbf{c}\in C_{H,r}\) whenever \(\Delta (\mathbf{y},\mathbf{c})\le 1\) for some codeword \(\mathbf{c}\), and outputs Fail otherwise.

Let \(S \subseteq \mathbb {F}_q^n\) be a linear subspace of dimension \(k\). Then \(N = \{ \mathbf{y}\in \mathbb {F}_q^n \mid \langle \mathbf{x},\mathbf{y}\rangle = 0 \text{ for every } \mathbf{x}\in S\} \) is itself a linear subspace of \(\mathbb {F}_q^n\), of dimension \(n-k\).

The span of \(k\) linearly independent vectors over \(\mathbb {F}_q\) has size exactly \(q^k\).

Every linear subspace \(S \subseteq \mathbb {F}_q^n\) contains the zero vector \(\mathbf{0}\).

Let \(\mathbf{y} = \mathbf{c}+\mathbf{e}_i\) where \(\mathbf{c}\in C_{H,r}\) and \(\mathbf{e}_i\) is the unit vector with its sole non-zero entry at position \(i\) (with the convention \(\mathbf{e}_0=\mathbf{0}\), corresponding to no error). Then \(\mathbf{H}_r\cdot \mathbf{y}^T = \mathbf{H}_r^i\), the \(i\)th column of \(\mathbf{H}_r\) (with the convention that \(\mathbf{H}_r^0 = \mathbf{0}\)).

Let \(p\) be a prime. Then \(\mathbb {F}_p = (\{ 0,1,\dots ,p-1\} , +_p, \cdot _p)\), where \(+_p\) and \(\cdot _p\) are addition and multiplication modulo \(p\), is a field.

Let \(V\) be a random variable such that \(\mathrm{Var}[V] \ne 0\). Then for any \(t {\gt} 0\),

Let \(q \ge 2\) be an integer and let \(0 \le \rho \le 1 - 1/q\). Then for any real \(m \ge 1\) such that

we have \(H_q(\rho ) \ge H_{q^m}(\rho )\).

Let \(E\) be any event. Then

For every \(0 {\lt} y \le 1 - 1/q\) and for every small enough \(\varepsilon {\gt} 0\),

where \(c'_q \ge 1\) is a constant that depends only on \(q\).

Let \(V\) be a non-negative random variable. Then for any \(t {\gt} 0\),

In particular, for any \(a \ge 1\), \(\Pr [V \ge a \cdot \mathbb {E}[V]] \le \frac{1}{a}\).

For any \(m \ge 1\), the distribution \(\mathscr {U}_{\mathbb {D}_1 \times \mathbb {D}_2 \times \cdots \times \mathbb {D}_m}\) is identical to the distribution \(\mathscr {U}_{\mathbb {D}_1} \times \mathscr {U}_{\mathbb {D}_2} \times \cdots \times \mathscr {U}_{\mathbb {D}_m}\).

Given a non-zero vector \(\mathbf{m} \in \mathbb {F}_q^k\) and a uniformly random \(k \times n\) matrix \(G\) over \(\mathbb {F}_q\), the vector \(\mathbf{m} \cdot G\) is uniformly distributed over \(\mathbb {F}_q^n\).

For any two events \(A\) and \(B\) defined on the same domain and probability distribution,

Let \(\mathbf{v}_1,\ldots ,\mathbf{v}_m \in \mathbb {R}^N\) be non-zero vectors.

1. If \(\langle \mathbf{v}_i,\mathbf{v}_j \rangle \le 0\) for all \(i \ne j\), then \(m \le 2N\).

2. Let \(\mathbf{v}_i\) be unit vectors for \(1 \le i \le m\). Further, if \(\langle \mathbf{v}_i,\mathbf{v}_j \rangle \le -\varepsilon {\lt} 0\) for all \(i \ne j\), then \(m \le 1 + \frac{1}{\varepsilon }\).

Algorithm 106 (Algorithm 4.2.1) terminates in \(q^{O(n)}\) time and outputs a code \(C \subseteq [q]^n\) with \(\Delta (C) \ge d\). Moreover, upon termination,

Let \(q\) be a prime power, \(0 \le \delta {\lt} 1-\frac{1}{q}\) and \(0 \le \varepsilon \le 1 - H_q(\delta )\). Let \(n\) be an integer and \(k = n(1-H_q(\delta )-\varepsilon )\). If a \(k \times n\) matrix \(\mathbf{G}\) over \(\mathbb {F}_q\) is picked uniformly at random, then with probability strictly greater than \(1 - q^{-\varepsilon n}\) the matrix \(\mathbf{G}\) has full rank and generates a linear code of rate \(1-H_q(\delta )-\varepsilon \) and relative distance at least \(\delta \).

For every pair of positive integers \(n,q\) and real \(\delta \in [0,1]\), writing \(d = \delta n\), there exists an \((n,k,d)_q\) code satisfying

In particular, for every positive integer \(q\) and real \(\delta \in [0, 1-1/q]\) there exists an infinite family of \(q\)-ary codes \(\mathscr {C}\) of rate \(R\) and relative distance \(\delta \) satisfying \(R \ge 1 - H_q(\delta )\).

For every \(q\) and \(n\), there exists a function \(f : [q]^n \longrightarrow \mathbb {R}^{nq}\) such that for every \(\mathbf{c}_1,\mathbf{c}_2 \in [q]^n\) we have

Consequently:

1. For every \(\mathbf{c} \in [q]^n\), \(\| f(\mathbf{c})\| = 1\).

2. If \(\Delta (\mathbf{c}_1,\mathbf{c}_2) \ge d\) then \(\langle f(\mathbf{c}_1),f(\mathbf{c}_2)\rangle \le 1 - \left(\frac{q}{q-1}\right)\left(\frac{d}{n}\right)\).

A finite union of proper linear subspaces of \(\mathbb {R}^N\) is not all of \(\mathbb {R}^N\).

Let \(E(x) \in \mathbb {F}_q[x]\) be an irreducible polynomial of degree \(s\). Then \(\mathbb {F}_q[x]/E(x)\) is a field of size \(q^s\).

The minimum distance of the Reed-Solomon code \(\mathrm{RS}\) of Definition 128 is \(n - k + 1\).

The Reed-Solomon code \(\mathrm{RS}\) of Definition 128 is a linear code.

Let \(E^*:\{ 0,1\} ^k\to \{ 0,1\} ^n\) and \(D^*:\{ 0,1\} ^n\to \{ 0,1\} ^k\) satisfy

where \(\mathbf{m}\) is uniform on \(\{ 0,1\} ^k\). List the messages as \(\mathbf{m}_1,\ldots ,\mathbf{m}_{2^k}\) and let \(P_i=\Pr _{\mathbf{e}\sim \mathrm{BSC}_p}[D^*(E^*(\mathbf{m}_i)+\mathbf{e})\ne \mathbf{m}_i]\); assume \(P_1\le P_2\le \cdots \le P_{2^k}\). Then \(P_{2^{k-1}}\le 2\cdot 2^{-\delta 'n}\).

Let \(0\le p{\lt}\tfrac 12\) and \(0\le \varepsilon \le \tfrac 12-p\). For large enough \(n\), if \(k\ge \lceil (1-H(p)+\varepsilon )n\rceil \) then for every pair of encoding and decoding functions \(E:\{ 0,1\} ^k\to \{ 0,1\} ^n\) and \(D:\{ 0,1\} ^n\to \{ 0,1\} ^k\), there exists \(\mathbf{m}\in \{ 0,1\} ^k\) such that

Let \(0\le p{\lt}\tfrac 12\) and \(0{\lt}\varepsilon \le \tfrac 12-p\). For large enough \(n\), there exists a real \(\delta {\gt}0\), an encoding function \(E:\{ 0,1\} ^k\to \{ 0,1\} ^n\) and a decoding function \(D:\{ 0,1\} ^n\to \{ 0,1\} ^k\) where \(k\le \lfloor (1-H(p+\varepsilon ))n\rfloor \), such that the following holds for every \(\mathbf{m}\in \{ 0,1\} ^k\):

Let \(0\le p{\lt}\tfrac 12\), \(0{\lt}\varepsilon \le \tfrac 12-p\), and let \(\varepsilon '=\varepsilon /2\). Let \(k\le \lfloor (1-H(p+\varepsilon ))n\rfloor \). Suppose \(E:\{ 0,1\} ^k\to \{ 0,1\} ^n\) is chosen at random by picking \(E(\mathbf{m}')\) independently and uniformly at random from \(\{ 0,1\} ^n\) for every \(\mathbf{m}'\in \{ 0,1\} ^k\), and let \(D\) be the maximum likelihood decoding (MLD) function for \(E\). Then there is \(\delta '=\delta '(\varepsilon ,p){\gt}0\) such that for every fixed \(\mathbf{m}\in \{ 0,1\} ^k\) and large enough \(n\),

Let \(q \geq 2\) be an integer and let \(0 \leq x \leq 1 - \frac1q\). Then the following inequalities hold:

where the second inequality is strict for \(x {\gt} 0\).

Let \(q \geq 2\) be an integer, \(0 {\lt} \rho {\lt} 1 - \frac1q\) a real number, and \(L \geq 1\) an integer. Then there exists a \((\rho , L)\)-list decodable code with rate

Let \(q \geq 2\) be an integer and \(0 {\lt} \rho {\lt} 1 - \frac1q\) a real number. For every \((\rho , L)\) code \(C\) of rate \(1 - H_q(\rho ) + \varepsilon \), it is necessary that \(L \geq 2^{\Omega (\varepsilon n)}\).

Let \(C\) be an \((n,k,d)_q\) code. If we fix the values in \(n-d+1\) out of the \(n\) positions in a possible codeword, then at most one codeword in \(C\) can agree with the fixed values.

Given a \(q\)-ary code \(C \subseteq [q]^n\) and \(0 \le e \le n\), there exists a Hamming ball of radius \(e\) containing at least \(\dfrac {|C|\, \mathrm{Vol}_q(e,n)}{q^n}\) codewords of \(C\).

For \(i, \ell \in \{ 0,1,\dots ,n\} \),

where \(a\) is an arbitrary vector in \(\{ 0,1\} ^n\) of Hamming weight \(i\) (the sum on the right does not depend on the choice of such \(a\), by symmetry).

Let \(d \le n\), and suppose \(\beta _1,\dots ,\beta _n \ge 0\) are real numbers such that

Then every binary code \(C \subseteq \{ 0,1\} ^n\) of minimum distance at least \(d\) satisfies

If \(q,r,s,t,s',t',b\) are non-negative integers such that \(r = s(q-1)+t\), \(r-b = s'(q-1)+t'\), \(t,t' \leq q-2\) and \(b \leq q-1\), then

Let \(q,r,s,t\) be non-negative real numbers such that \(q \geq 2\), \(r = s(q-1)+t\) and \(t \leq q-2\). Then

A nonzero univariate polynomial \(f(X)\) of degree \(t\) over a field \(\mathbb {F}_q\) has at most \(t\) distinct roots in \(\mathbb {F}_q\). (This restates Prop. 5.1.5 of the book. It is deliberately restated locally rather than cited across chapters, since the corresponding Ch5 label is not part of the canonical cross-chapter table used to build this blueprint.)

For every finite field \(\mathbb {F}_q\) and every \(a \in \mathbb {F}_q\), \(a^q - a = 0\).

For fixed \(m\), \(K_{q,m,r}\) is monotone non-decreasing in \(q\) and in \(r\).

Let \(P \in \mathbb {F}_q[X_1,\ldots ,X_m]\) be such that \(\deg _{X_i}(P) \leq q-1\) for every \(i \in [m]\), and suppose \(P(\mathbf{a}) = 0\) for every \(\mathbf{a} \in \mathbb {F}_q^m\). Then \(P = 0\) as a polynomial. Consequently, for every \(\mathbf{d} \in S_{q,m,r}\) (Definition 193) the evaluations of the monomials \(\mathbf{X}^{\mathbf{d}}\) are linearly independent, and (together with the fact that they span \(\mathrm{RM}(q,m,r)\)) they form a basis for \(\mathrm{RM}(q,m,r)\).

Let \(f\) be a non-zero polynomial from \(\mathbb {F}_2[X_1,\ldots ,X_m]\) with \(\deg _{X_i}(f) \leq 1\) for every \(i \in [m]\). Then

Let \(f\) be a non-zero polynomial from \(\mathbb {F}_q[X_1,\ldots ,X_m]\) with \(\deg _{X_i}(f) \leq q-1\) for every \(i \in [m]\) and \(\deg (f) \leq r\). Furthermore, let \(s,t\) be the unique non-negative integers such that \(t \leq q-2\) and

Then

Hence \(\mathrm{RM}(q,m,r)\) has distance at least \(q^{m - \frac{r}{q-1}}\).

Let \(f \in \mathbb {F}_q[X_1,\ldots ,X_m]\) be a non-zero polynomial with \(\deg (f) \leq r\). Then the fraction of zeroes of \(f\) is at most \(\frac{r}{q}\), i.e.,

For events \(\mathcal{E}_1, \mathcal{E}_2\) in a common probability space, \(\Pr [\mathcal{E}_1 \cup \mathcal{E}_2] \leq \Pr [\mathcal{E}_1] + \Pr [\mathcal{E}_2]\).

If \(C_{out} \subseteq \mathbb {F}_{q^k}^N\) is an \(\mathbb {F}_{q^k}\)-linear code and \(C_{in} \subseteq \mathbb {F}_q^n\) is an \(\mathbb {F}_q\)-linear code of dimension \(k\), then (using an \(\mathbb {F}_q\)-linear identification of \(\mathbb {F}_{q^k}\) with \(\mathbb {F}_q^k\) to instantiate the bijection of Definition 202) the code \(C_{out}\circ C_{in} \subseteq \mathbb {F}_q^{nN}\) is \(\mathbb {F}_q\)-linear.

For every \(\alpha \in \mathbb {F}_{q^k}^*\), the code \(C_{in}^\alpha \) of Definition 207 is \(\mathbb {F}_q\)-linear and strongly explicit.

Fix a prime power \(q\) and \(\varepsilon {\gt}0\). Let \(C_{out}\) be a \(q^k\)-ary code meeting the Singleton bound (Theorem 110) with rate \(R\), i.e. with relative distance \(\delta _{out} \ge 1-R\) (for instance a Reed–Solomon code, Definition 128, by Theorem 131), and let \(C_{in}\) be a \(q\)-ary code meeting the Gilbert–Varshamov bound (Theorem 105) with rate \(r{\gt}0\), i.e. with relative distance \(\delta _{in} \ge H_q^{-1}(1-r) - \varepsilon \). Then \(C := C_{out}\circ C_{in}\) has rate \(rR\) and relative distance \(\delta = (1-R)\big(H_q^{-1}(1-r)-\varepsilon \big)\). Consequently, expressing \(R\) as a function of \(\delta \) and \(r\), and optimizing over the choice of \(r\), the rate of such a concatenated code satisfies

where the constraint \(r {\lt} 1-H_q(\delta +\varepsilon )\) is exactly what is needed to ensure the maximized quantity is positive. This lower bound on the rate (as a function of the relative distance \(\delta \)) is called the Zyablov bound.

If \(G\) is a \((\gamma ,\varepsilon )\)-disperser and \(\Delta (C) \ge \gamma n\), then \(\Delta (G(C)) \ge (1-\varepsilon )m\), where \(n=|L|\) and \(m=|R|\).

\(R(G(C)) = \frac{1}{c}\cdot R(C)\).

Let \(G\) be an \((n,m,c,\gamma ,\alpha )\) bipartite expander. Then there exists another bipartite graph \(G'\) that is an \((n,m',c,\gamma ,\alpha )\) bipartite expander such that

• \(m \le m' \le 2m\);

• every right vertex in \(G'\) has degree at most \(\left\lceil \frac{nc}{m}\right\rceil \).

Let \(q=2^s\) for integer \(s \ge 1\). Let \(C_{\text{out}}:\mathbb {F}_q^k \to (\mathbb {F}_q^b)^n\) and \(C_{\text{in}}:\mathbb {F}_q^b \to \mathbb {F}_q^B\) be \(\mathbb {F}_2\)-linear codes of relative distance \(\delta _{\text{out}}\) and \(\delta _{\text{in}}\) respectively. Let \(G\) be the double cover of an \((n,B,\lambda )\)-expander. Then if \(\lambda \le \varepsilon \sqrt{\delta _{\text{out}}}B\) then \(\delta (\mathscr {CA}(C_{\text{out}},C_{\text{in}},G)) \ge \delta _{\text{in}}-\varepsilon \).

1. Let \(G=(L,R,E)\) be an \((n,m,c,\gamma ,\alpha )\)-bipartite-expander with \(\alpha \cdot \gamma \ge (1-\varepsilon )m/n\). Then \(G\) is a \((\gamma ,\varepsilon )\)-disperser.

2. Let \(G\) be an \((n,d,\lambda )\)-spectral expander. Then the double cover \(H\) of \(G\) is a \(d\)-regular \((\gamma ,\varepsilon )\)-disperser for \(\varepsilon = \frac{\lambda ^2}{\gamma d^2}\).

Let \(X = (V,E)\) be a \((n,d,\lambda )\)-graph. Then for every \(A,B \subseteq V\) (possibly \(A=B\)) we have

In particular, this implies

For every \(\varepsilon ,\gamma {\gt} 0\) and for every large enough \(d\), there is an explicit (poly-time constructible) family of \(d\)-regular \((\gamma ,\varepsilon )\)-dispersers on \(n\) left and right vertices, for every sufficiently large \(n\). Furthermore one can take \(d = \Theta \left(\frac{1}{\gamma \varepsilon }\right)\).

Every real symmetric \(n \times n\) matrix has \(n\) real eigenvalues (counted with multiplicity). In particular, since the adjacency matrix of a graph on \(n\) vertices is real and symmetric, we may associate to the graph the \(n\) eigenvalues \(\lambda _1 \ge \lambda _2 \ge \cdots \ge \lambda _n\) of its adjacency matrix.

The dimension of \(X(G,C_0)\) is at least \(n - m(d - \dim (C_0))\).

Let \(G = (L,R,E)\) be an \((n,m,c,\gamma ,c(1-\varepsilon ))\) bipartite expander with \(\varepsilon {\lt} 1/2\). Then for every \(S \subseteq L\) with \(|S| \le \gamma n\), we have

For every input sequence \(\{ (\alpha _i,y_i)\} _{i=1}^n\) with \(\alpha _i\) distinct and every \(\ell \ge 1\), Step 1 of Algorithm 266 has a non-zero solution \(Q(X,Y)\) with \(\deg _X(Q) \le \ell \) and \(\deg _Y(Q) \le n/\ell \) satisfying \(Q(\alpha _i,y_i)=0\) for all \(1 \le i \le n\).