Recap: Expanders and Coding Theory

We looked at applications of Expanders to Coding Theory and saw that they could be used to obtain efficient encoding and decoding algorithms, with good error-detection and recovery properties.

We first considered codes which used the adjacency matrix of a bipartite expander as the parity check matrix. The simple FLIP algorithm allowed us to decode from a constant fraction of errors in linear time. In this algorithm, vertices of the left partite set are labelled with the bits of the received word, and a vertex of the right partite set is satisfed if an even number of its neighbors are set to '1'. As long as any vertex on the left has more unsatisfied than satisfied neighbors, we flip the bit corresponding to that vertex.

A similar idea could be tried for efficient encoding, but in order to obtain a linear time algorithm, the adjacency matrix must be sparse. Codes with low-density generating matrices have poor error correcting capabilities, but Spielman showed that such codes could be used for error reduction. Using Spielman's error-reducing codes, we can inductively construct error-correcting codes which allow linear-time encoding.

Another use of expanders is in the algorithm of Alon, Bruck, Naor, Naor and Roth; their construction allows us to obtain linear-time encodable and decodable codes with very large minimum distance (and hence good error correction); the price we pay is a significantly increased alphabet size. Finally, we considered list decoding, in which we output all codewords (not just the nearest codeword) that are sufficiently close to the received word. The ABNNR construction allowed us to construct a (1,2,2)-list recoverable code: that is, if in the received codeword, we have a list of two possible symbols for each position of the codeword, we output each of the (at most 2) codewords that are compatible with all the lists. We also saw that a similar construction could be used to obtain list-decodable codes from list-recoverable codes.

Recap: The PCP Theorem by Gap Amplification

The PCP theorem (almost) states this surprising property that given a proof of answer of some YES/NO problem, there is some scheme that checks just some constant pieces of the proof and decides whether the proof is correct or not, and this decision is with high probability a correct decision.

It is almost easily known that NP-hardness of GAP-3SAT problem is equivalent to correctness of PCP theorem where GAP-3SAT is the following problem: given a 3-SAT formula and a real number c, whether the formula is satisfiable or under every truth assignment at least c fraction of clauses remain unsatisfied. It is obvious that for small values of c this problem is NP-hard (since it is just SAT for small c), so the difficult question is the case of larger c values. Arora and Safra established a proof of PCP theorem which was long and algebraic. This paper presents a more combinatorial proof using reduction of a variant of GAP-3SAT for small values of c to the same variant of GAP-3SAT for larger values (actually constant values) of c. The variant of 3SAT is this: given a graph where each vertex of graph is a variable over a finite alphabet and each edge is a relation over that alphabet, and given a real value c, whether there is satisfying assignment to the vertices of the graph or always c fraction of edges remain unsatisfied.

The tool to prove this, is almost a standard approach: first we convert the graph to an expander using replacement and graph superimposition (union of a graph with an expander). Then using powering (an operation similar to zigzag product) we increase the "expansion" in the graph and it turns out that this increases the fraction of unsatisfied edges. In the last step using a technical method we decrease the size of the alphabet of the graph (which the powering operation increases that by an exponential factor). All these operations can be done in polytime and as a result the farction of unsatisfied edges double. If we repeat these steps for a logarithmic number of times, the fraction of unsatisfied edges becomes as large as a constant, which is the desired property.

Recap: Extractors

For randomization it is common practice to assume some uniformally random source. However, such an assumption is unrealistic as most sources found in nature are biased. We therefore wish to utilize these biased sources of randomness to produce a perfectly random source. For some cases, this can be accomplished deterministically, however for many sources this is not the case. An example of which are Santha-Vazirani sources (δ-SV sources defined in the post of 10/22/05).
By construction of a δ-SV-source for any deterministic extractor of even a single bit such that the extractor using the source is as biased as the source itself in Proposition 1 we showed this.

A (k, ε)-extractor is then a function which takes some purely random seed of length d and any k-source X on {0,1}ⁿ and outputs some m length bitstring which is ε-close to unifom.
The proof of the existence of such extractors comes from the application of the probabilistic method considering a random choice of deterministic extractors (zero length seeds).
Constructive proofs such as the Leftover Hash Lemma guarantee extractors with specific bounds (A table of some of these bounds is located in the post of 10/22/05).

Extractors and expanders are interrelated as any extractor Ext: {0,1}ⁿ × {0,1}^d → {0,1}^m can be viewed as a bipartite multigraph G = { [N], [M], E } where an edge exists between v ∈ [N] and u ∈ [M] if and only if for some random seed the extractor on u outputs v.
On expection of the resulting graph the extraction property is equivalent to the expander mixing lemma thus the graph is an expander.
Similarly an expander can be used to create an extractor by making the expander into a bipartite graph in the usual way.

In the end we examined extractors over block sources. A block source is a generalization of a δ-SV-source where single bits are replaced with constant sized blocks of bits. Such sources can be used by extractors via the repeated application of an extractor on the individual blocks of the source. In doing so, the initial seed is applied only to the first iteration of the extractor generating some random bitstring r_iz_i. On the next iteration i - 1 the r_i bits resulting from the previous extraction are used as the seed. The resulting output is then r₁z₁z₂...z_i (note that the first iteration is i and each subsequent iteration has index i - 1). The proof of these bits' randomness is found by induction.