Expander code

In coding theory, expander codes form a class of error-correcting codes that are constructed from bipartite expander graphs. Along with Justesen codes, expander codes are of particular interest since they have a constant positive rate, a constant positive relative distance, and a constant alphabet size. In fact, the alphabet contains only two elements, so expander codes belong to the class of binary codes. Furthermore, expander codes can be both encoded and decoded in time proportional to the block length of the code. Expander codes are the only known asymptotically good codes which can be both encoded and decoded from a constant fraction of errors in polynomial time.

Expander codes

In coding theory, an expander code is a $[n,n-m]_{2}\,$ linear block code whose parity check matrix is the adjacency matrix of a bipartite expander graph. These codes have good relative distance $2(1-\varepsilon )\gamma \,$, where $\varepsilon \,$ and $\gamma \,$ are properties of the expander graph as defined later), rate $\left(1-{\tfrac {m}{n}}\right)\,$, and decodability (algorithms of running time $O(n)\,$ exist).

Definition

Consider a bipartite graph $G(L,R,E)\,$, where $L\,$ and $R\,$ are the vertex sets and $E\,$ is the set of edges connecting vertices in $L\,$ to vertices of $R\,$. Suppose every vertex in $L\,$ has degree $d\,$ (the graph is $d\,$-regular), $|L|=n\,$, and $|R|=m\,$, $m<n\,$. Then $G\,$ is a $(N,M,d,\gamma ,\alpha )\,$ expander graph if every small enough subset $S\subset L\,$, $|S|\leq \gamma n\,$ has the property that $S\,$ has at least $d\alpha |S|\,$ distinct neighbors in $R\,$. Note that this holds trivially for $\gamma \leq {\tfrac {1}{n}}\,$. When ${\tfrac {1}{n}}<\gamma \leq 1\,$ and $\alpha =1-\varepsilon \,$ for a constant $\varepsilon \,$, we say that $G\,$ is a lossless expander.

Since $G\,$ is a bipartite graph, we may consider its $n\times m\,$ adjacency matrix. Then the linear code $C\,$ generated by viewing the transpose of this matrix as a parity check matrix is an expander code.

It has been shown that nontrivial lossless expander graphs exist. Moreover, we can explicitly construct them.

Rate

The rate of $C\,$ is its dimension divided by its block length. In this case, the parity check matrix has size $m\times n\,$, and hence $C\,$ has dimension at least $(n-m)/n=1-{\tfrac {m}{n}}\,$.

Distance

Suppose $\varepsilon <{\tfrac {1}{2}}\,$. Then the distance of a $(n,m,d,\gamma ,1-\varepsilon )\,$ expander code $C\,$ is at least $2(1-\varepsilon )\gamma n\,$.

Proof

Note that we can consider every codeword $c\,$ in $C\,$ as a subset of vertices $S\subset L\,$, by saying that vertex $v_{i}\in S\,$ if and only if the $i\,$th index of the codeword is a 1. Then $c\,$ is a codeword iff every vertex $v\in R\,$ is adjacent to an even number of vertices in $S\,$. (In order to be a codeword, $cP=0\,$, where $P\,$ is the parity check matrix. Then, each vertex in $R\,$ corresponds to each column of $P\,$. Matrix multiplication over ${\text{GF}}(2)=\{0,1\}\,$ then gives the desired result.) So, if a vertex $v\in R\,$ is adjacent to a single vertex in $S\,$, we know immediately that $c\,$ is not a codeword. Let $N(S)\,$ denote the neighbors in $R\,$ of $S\,$, and $U(S)\,$ denote those neighbors of $S\,$ which are unique, i.e., adjacent to a single vertex of $S\,$.

Lemma 1

For every $S\subset L\,$ of size $|S|\leq \gamma n\,$, $d|S|\geq |N(S)|\geq |U(S)|\geq d(1-2\varepsilon )|S|\,$.

Proof

Trivially, $|N(S)|\geq |U(S)|\,$, since $v\in U(S)\,$ implies $v\in N(S)\,$. $|N(S)|\leq d|S|\,$ follows since the degree of every vertex in $S\,$ is $d\,$. By the expansion property of the graph, there must be a set of $d(1-\varepsilon )|S|\,$ edges which go to distinct vertices. The remaining $d\varepsilon |S|\,$ edges make at most $d\varepsilon |S|\,$ neighbors not unique, so $U(S)\geq d(1-\varepsilon )|S|-d\varepsilon |S|=d(1-2\varepsilon )|S|\,$.

Corollary

Every sufficiently small $S\,$ has a unique neighbor. This follows since $\varepsilon <{\tfrac {1}{2}}\,$.

Lemma 2

Every subset $T\subset L\,$ with $|T|<2(1-\varepsilon )\gamma n\,$ has a unique neighbor.

Proof

Lemma 1 proves the case $|T|\leq \gamma n\,$, so suppose $2(1-\varepsilon )\gamma n>|T|>\gamma n\,$. Let $S\subset T\,$ such that $|S|=\gamma n\,$. By Lemma 1, we know that $|U(S)|\geq d(1-2\varepsilon )|S|\,$. Then a vertex $v\in U(S)\,$ is in $U(T)\,$ iff $v\notin N(T\setminus S)\,$, and we know that $|T\setminus S|\leq 2(1-\varepsilon )\gamma n-\gamma n=(1-2\varepsilon )\gamma n\,$, so by the first part of Lemma 1, we know $|N(T\setminus S)|\leq d(1-2\varepsilon )\gamma n\,$. Since $\varepsilon <{\tfrac {1}{2}}\,$, $|U(T)|\geq |U(S)\setminus N(T\setminus S)|\geq |U(S)|-|N(T\setminus S)|>0\,$, and hence $U(T)\,$ is not empty.

Corollary

Note that if a $T\subset L\,$ has at least 1 unique neighbor, i.e. $|U(T)|>0\,$, then the corresponding word $c\,$ corresponding to $T\,$ cannot be a codeword, as it will not multiply to the all zeros vector by the parity check matrix. By the previous argument, $c\in C\implies wt(c)\geq 2(1-\varepsilon )\gamma n\,$. Since $C\,$ is linear, we conclude that $C\,$ has distance at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2(1-\varepsilon)\gamma n\,} .

Encoding

The encoding time for an expander code is upper bounded by that of a general linear code - Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n^2)\,} by matrix multiplication. A result due to Spielman shows that encoding is possible in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)\,} time.

Decoding

Decoding of expander codes is possible in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n)\,} time when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon < \tfrac{1}{4}\,} using the following algorithm.

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i\,} be the vertex of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L\,} that corresponds to the $i\,$th index in the codewords of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C\,} . Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y \in \{0,1\}^n\,} be a received word, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V(y) = \{v_i | \text{ the } i^{\text{th}} \text{ position of } y \text{ is a } 1\}\,} . Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e(i)\,} be Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\{v \in R | N(v) \cap V(y)\,} is evenFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \}|\,} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle o(i)\,} be $|\{v\in R|N(v)\cap V(y)\,$ is oddFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \}|\,} . Then consider the greedy algorithm:

---

Input: received codeword Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y\,} .

initialize y' to y
while there is a v in R adjacent to an odd number of vertices in V(y')
if there is an i such that o(i) > e(i)
flip entry i in y'
else
fail

Output: fail, or modified codeword Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y'\,} .

---

Proof

We show first the correctness of the algorithm, and then examine its running time.

Correctness

We must show that the algorithm terminates with the correct codeword when the received codeword is within half the code's distance of the original codeword. Let the set of corrupt variables be Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S\,} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s = |S|\,} , and the set of unsatisfied (adjacent to an odd number of vertices) vertices in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R\,} be Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c\,} . The following lemma will prove useful.

Lemma 3

If $0<s<\gamma n\,$, then there is a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i\,} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle o(i) > e(i)\,} .

Proof

By Lemma 1, we know that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U(S) \geq d(1-2\varepsilon)s\,} . So an average vertex has at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d(1-2\varepsilon) > d/2\,} unique neighbors (recall unique neighbors are unsatisfied and hence contribute to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle o(i)\,} ), since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon < \tfrac{1}{4}\,} , and thus there is a vertex Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i\,} with $o(i)>e(i)\,$.

So, if we have not yet reached a codeword, then there will always be some vertex to flip. Next, we show that the number of errors can never increase beyond Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma n\,} .

Lemma 4

If we start with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s < \gamma(1-2\varepsilon)n\,} , then we never reach Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s = \gamma n\,} at any point in the algorithm.

Proof

When we flip a vertex Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i\,} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle o(i)\,} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e(i)\,} are interchanged, and since we had Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle o(i) > e(i)\,} , this means the number of unsatisfied vertices on the right decreases by at least one after each flip. Since $s<\gamma (1-2\varepsilon )n\,$, the initial number of unsatisfied vertices is at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d\gamma(1-2\varepsilon)n\,} , by the graph's Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d\,} -regularity. If we reached a string with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma n\,} errors, then by Lemma 1, there would be at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d\gamma(1-2\varepsilon)n\,} unique neighbors, which means there would be at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d\gamma(1-2\varepsilon)n\,} unsatisfied vertices, a contradiction.

Lemmas 3 and 4 show us that if we start with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s < \gamma(1-2\varepsilon)n\,} (half the distance of $C\,$), then we will always find a vertex Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i\,} to flip. Each flip reduces the number of unsatisfied vertices in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R\,} by at least 1, and hence the algorithm terminates in at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m\,} steps, and it terminates at some codeword, by Lemma 3. (Were it not at a codeword, there would be some vertex to flip). Lemma 4 shows us that we can never be farther than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma n\,} away from the correct codeword. Since the code has distance Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2(1-\varepsilon)\gamma n > \gamma n\,} (since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon < \tfrac{1}{2}\,} ), the codeword it terminates on must be the correct codeword, since the number of bit flips is less than half the distance (so we couldn't have traveled far enough to reach any other codeword).

Complexity

We now show that the algorithm can achieve linear time decoding. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac{n}{m}\,} be constant, and $r\,$ be the maximum degree of any vertex in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R\,} . Note that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r\,} is also constant for known constructions.

1. Pre-processing: It takes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(mr)\,} time to compute whether each vertex in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R\,} has an odd or even number of neighbors.
2. Pre-processing 2: We take Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(dn) = O(dmr)\,} time to compute a list of vertices Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i\,} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L\,} which have $o(i)>e(i)\,$.
3. Each Iteration: We simply remove the first list element. To update the list of odd / even vertices in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R\,} , we need only update Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(d)\,} entries, inserting / removing as necessary. We then update Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(dr)\,} entries in the list of vertices in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L\,} with more odd than even neighbors, inserting / removing as necessary. Thus each iteration takes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(dr)\,} time.
4. As argued above, the total number of iterations is at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m\,} .

This gives a total runtime of $O(mdr)=O(n)\,$ time, where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d\,} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r\,} are constants.

See also

• Expander graph
• Low-density parity-check code
• Linear time encoding and decoding of error-correcting codes
• ABNNR and AEL codes

Notes

This article is based on Dr. Venkatesan Guruswami's course notes.

Source

http://wikipedia.org/