Extractors (Phillip Mienk, lecturer)

Motivation: For most of what we've been talking about in the past, we've been assuming we've had perfectly random sources, but these creatures simply can't always be found in "nature." The question then arises -- can we take a source which is biased and bring it as close as possible to purely random?

We take to start a result from vonNeumann: For any $X$₁, X₂,...,X_n∈{0,1} with Pr[X_i = 1] = δ_i, where 0<δ≤δ_i≤1-δ, then for l such bits, we can bound the parity to be exponentially close to 1/2. That is, |Pr[ XOR_i=1...l X_i = 1] - ¹/₂| = 2 ^-Ω(l).

δ-SV-sources (Santha-Vazirani): ∀i ∀x₁, ..., x_i-1 such that δ≤Pr[X_i=1 | X₁=x₁, ..., X_i-1=x_i-1] ≤ 1-δ

Proposition 1: ∀δ for all deterministic extractors f(x)=b (functions which output one bit), ∃ an SV-source X such that Pr[b = 1] is as biased as the SV-source.
Proof: Consider X_i, ..., X_n ∈ D = {0,1}ⁿ. Let f(x)=b. Note that |D|=2ⁿ. Divide the domain, D, into two pieces, D₀ where the extractor outputs 0, and D₁ where the extractor outputs 1. D₀={x: f(x)=0}, D₁={x: f(x)=1}. We want to show there is an SV-source such that f is δ-biased; if the uniform distribution doesn't work, then the difference between the sizes of our two domains must be | |D₀| - |D₁| | ≤ 2ⁿδ. WLOG, we say |D₀| ≥ |D₁|. Then there are |D₀|≤ (²ⁿ/₂) + (^2nδ/₂) = ^{(1 + δ)}/₂ ·2ⁿ. Thus, |D₁|≥ ^{(1 - δ)}/₂ ·2ⁿ. Let X be an SV-source such that ^{(1 + δ)}/₂ on D₀ and ^{(1 - δ)}/₂ on D₁. If x ∈ D₀, Pr[x] = ^{(1 + δ)}/₂ · ¹/_|D0|. If x ∈ D₁, Pr[x] = ^{(1 - δ)}/₂ · ¹/_|D1|. Now let's say we have strings a=y0 and b=y1, where |y|=n-1 (we would like to show that |Pr[a|y]-Pr[b|y]|<δ). It is enough to bound the ratio of ^Pr[a|y]/_Pr[b|y] = ^Pr[a]/_Pr[b]. If a,b∈D₀ or a,b∈D₁, this ratio is obviously exactly 1; thus we assume WLOG that a∈D₀ and b∈D₁. Then, ^Pr[a]/_Pr[b] = (^{(1 + δ)}/₂ · ¹/_|D0|)/(^{(1 - δ)}/₂ · ¹/_|D1|) = ^{(1 + δ)}/_{(1 - δ)} · ^|D₁|/_|D0| ≤^{(1 + δ)}/_{(1 - δ)}. With some more elementary algebra (which would just look overly intimidating with the terrible typsetting on this blog), we can also get a lower bound of 1. Thus, for all f we have constructed a δ-SV-source, namely ^(1+δ)/₂ on D₀, ^(1-δ)/₂ on D₁.

More motivation: Why are we doing this? We want to run randomized algorithms given an extractor and input. If it doesn't yield significantly random output, then we can allow a purely random seed into the extractor, and we hope that this will make the output more uniformly random. From an algorithm A(w,r) we can make a new algorithm A'(w,X) with the same input and k-source X and generates all possible bits it can from a given seed, d. For small d, we can iterate over all seeds until we find the one that gives optimal output, and thus we'd like to prove there exist extractors with small seeds.

Definition: Ext: {0,1}ⁿ × {0,1}^d → {0,1}^m is a (k,ε)-extractor if for any k-source X on {0,1}ⁿ then Ext(X,U_d) is ε-close to U_m.

Definition: The statistical difference, Δ, is half the L₁-difference. That is, Δ(x,y) = max_T⊆U |Pr[x∈T]-Pr[y∈T]|

Definition: Supp(X)={x : x∈X, Pr[x]>0}

Proposition 2: For any n and for any k≤n, and a flat (uniform over {0,1}^k) k-source X, ∃ Ext: {0,1}ⁿ → {0,1}^m with m=k-2log(¹/_ε)-O(1) such that Ext(X) is ε-close to U_m.
Proof: Consider a random deterministic Extractor. We want ∀T ⊆ [2^m] |Pr[Ext(X)∈T] - Pr[U_m∈T]|≤ε. This would imply that ^{|{x∈supp(X) : Ext(x)∈T}|}/_2^k differs from density μ(T) by less than ε. (The rest of the proof is left to the reader, as class ended and notes were left incomplete.)

Deterministic Extractors: Fix Y a flat l-source on {0,1}^t. As there are L=2^l desired elements from T=2^t possible, we have (T choose L) candidates for Y. By Stirling's approximation, this is ≈(^Te/_L)^L. Consider a random extractor Ext: {0,1}^t → {0,1}^m. Pr[Ext not an extractor on Y] ≤ 2^Ω(Lε2). This implies that Pr[Ext not an extractor for some Y] ≤ (T choose L) · 2^-Ω(Lε2) ≤ (^Te/_L)^L · 2^-Ω(Lε2) > 1. Thus the deterministic extractor fails.

Randomized Extractors: Consider Y=(X,U_d), where X is a flat k-source with t=n+d. (Notation: T=2^t, N=2ⁿ, D=2^d, K=2^k). Then T=ND, L=KD, and there are (N choose K) candidates for Y. Pr[Ext fails for some Y] ≤ (N choose K) · 2^-Ω(KDε2) ≤ (^Ne/_K)^K · 2^-Ω(KDε2), which is less than 1 if d=log(n-k) + 2log(¹/_ε)+O(1). Since this probability is less than one, there is a high probability we have an extractor for all Y, and thus we can have randomized algorithms.

Recall that we're looking to find a small seed, d, while giving good output, m. What do we know?

	d	m
Necessary for BPP simulation	O(log n)	kΩ(1)
Pairwise Independant Hashing	O(n)	k+d-O(1)
Spectral Expanders	O(n-k)	n
Lu, Reingold, Vadhan, Widgerson	O(log n)	(1-γ)k, ∀γ>0
Zig-Zag Product	O(log2n)	k+d-O(1)

Definition: A family of functions H={h_i : [N] → [M]} is pairwise independent if
     (1) ∀x∈[N], h(x) is uniformally distributed in [M]
     (2) ∀x,y∈[N], x≠y, h(x) and h(y) are independent.

Leftover Hash Lemma: If H={h : {0,1}ⁿ → [0,1}^l} is a pairwise independent family where l=k-2log(¹/_ε)-O(1), then Ext(x,h) = (h, h(x)) is a (k,ε)-extractor. (Not enough time for the Proof in class)

Extractors and Expanders: We can interpret Ext: {0,1}ⁿ × {0,1}^d → {0,1}^m as a bipartite multigraph G=([N],[M],E) where (u,v)∈E iff ∃r∈U_d such that Ext(u,r)=v. Consider the extraction property that Ext is a (k,ε)-extractor iff ∀S⊆[N], |S|=K, Δ(Ext(U_s,U_d),U_m) = max_T⊆[M] |Pr[Ext(U_s,U_d)∈T] - Pr[U_m∈T]| ≤ ε Therefore, for any T⊆[M], this implies that |(^e(S,T)/_|S|·D) - (^|T|/_M)|≤ε. This looks familiar; recall the...

Expander Mixing Lemma: For S,T⊆G and λ the second largest eigenvalue of the adjacency matrix A, |(^E(S,T)/_|S|·|T|) - (^D/_N)| ≤ λ√(|S|·|T|). Note that we can make G bipartite by making a copy of G, selecting S in G₁, T in G₂, and if uv∈G, ∃uv∈G₁G₂ such that u∈G₁ and v∈G₂. Through some manipulation of the two similar equations, one can see that if λ is "small enough," an expander yields an extractor (and vice versa).

Definition: X is a (k,l) block source if X=B₁...B_t where ∀i∈[t], |B_i|=l and ∀b₁, ..., b_i-1∈{0,1}^l, B_i|_{B1=b1, ..., Bi-1=bi-1} is a k-source. Alternatively, X is a (k,l) block source if it can be partitioned into l blocks of equal size such taht conditional distribution of each block given previous history is a k-source.

Theorem: Given explicit construction for (k,ε)-extractor Ext: {0,1}^l × {0,1}^d → {0,1}^d+m, then ∀t≥1 ∃ Ext': {0,1}^tl × {0,1}^d → {0,1}^d+tm such that Ext'(X,U_d is tε-close to U_d+tm for all (k,l) block sources X with t blocks. Formally, consider Ext'. For x∈{0,1}^tl, x=b₁...b_t for |b_i|=l. For each b_i, Ext yields r_iz_i with |r_i|=d. Then Ext(b_i,r_i+1), where r_i+1 is the initial seed, d. Thus, &delta(Ext'(X,U_d), U_d+tm)≤tε
Proof: X=B₁...B_t. Let R₁, ..., R_t+1 and Z₁, ..., Z_t be random variables representing the output of Ext'(X,U_d) and internal output. Let M₁, ..., M_t be samples of U_m. Define ∀i∈[t+1]: D_i = (B₁, ..., B_i-1, R_i, Z_i, ..., Z_t) and E_i = (B₁, ..., B_i-1, U_d, M_i, ..., M_t). We want to show that Δ(D_i,E_i)≤(t+1-i)ε, and we shall proceed by induction. Base case: i=t+1. Since R_t+1 is a seed, it is uniform in U_d. Inductive hypothesis: Δ(D_i+1,E_i+1) ≤ ((t+1) - (i+1))ε ≤ (t-i)ε. Inductive step: &Delta (D_i+1,E_i+1) = Δ( (B₁, ..., B_i, R_i+1, Z_i+1, ..., Z_t), (B₁, ..., B_i, U_d, M_i+1, ..., M_t) ) = Δ( (B₁, ..., B_i, Ext(B_i, R_i+1), Z_i+1, ..., Z_t), (B₁, ..., B_i, Ext(B_i, U_d), M_i+1, ..., M_t) ). But Ext(B_i, R_i+1) = R_iZ_i. Thus, the same quantity = Δ(D_i, (B₁, ..., B_i, Ext(B_i, U_d), M_i+1, ..., M_t)). We know that B_i is a k-source conditioned on B₁, ..., B_i-1, that Ext is a (k,ε)-extractor, and that M_i, ..., M_t are independent. Thus, our quantity = Δ((B₁, ..., B_i, Ext(B_i, U_d), M_i+1, ..., M_t), (B_i, ..., B_i-1, U_d+m, M_i+1, ..., M_t))≤ε Consider the triangle inequality: &Delta(D_i, E_i)≤ Δ(D_i, (B₁, ..., B_i, Ext(B_i, U_d), M_i+1, ..., M_t)) + Δ((B₁, ..., B_i, Ext(B_i, U_d), M_i+1, ..., M_t), E_i) ≤ (t-i)ε + ε ≤ (t+1-i)ε

Since this has worked for any block source, we can then generate similarly for an SV-source.