10 Lossless conductors and expanders
A \(k\)-source is a distribution with min-entropy \(\ge k\); a \((k,\epsilon )\)-source is \(\epsilon \)-close in \(\ell _1\) to a \(k\)-source.
\(E:\{ 0,1\} ^n\times \{ 0,1\} ^d\to \{ 0,1\} ^m\) is a \((k_{\max },a,\epsilon )\)-conductor if for every \(k\le k_{\max }\) and every \(k\)-source \(X\), \(E(X,U_d)\) is a \((k+a,\epsilon )\)-source.
\(E\) is \((a,\epsilon )\)-extracting if it is an \((m-a,a,\epsilon )\)-conductor; \((k_{\max },\epsilon )\)-lossless if a \((k_{\max },d,\epsilon )\)-conductor; \(\langle E,C\rangle \) is a buffer conductor if \(E\) is extracting and \(\langle E,C\rangle \) is lossless; a permutation conductor if moreover \(\langle E,C\rangle \) is a permutation.
A left-\(D\)-regular bipartite \(G=(V_L,V_R;E)\), \(|V_L|=N\), \(|V_R|=M\), is a \((K_{\max },\epsilon )\)-lossless expander if every \(K\le K_{\max }\) left vertices have \(\ge (1-\epsilon )DK\) neighbours.
A \((k_{\max },\epsilon )\)-lossless conductor, read as a bipartite graph with \(N=2^n\), \(M=2^m\), \(D=2^d\), is a \((2^{k_{\max }},\epsilon )\)-lossless expander.
For bipartite \(H\) (\(d\)-regular, \(s\) per side) and bipartite \(G\) (\(s\)-regular, \(n\) per side), \(G\textcircled {z}H\) is the \(d^2\)-regular bipartite graph on \(sn\) per side defined by dashed–wiggly–dashed steps.
For any \((X_1,X_2)\), \(\epsilon \), \(a\), there is \((Y_1,Y_2)\) \(\epsilon \)-close to \((X_1,X_2)\) that is a convex combination of two distributions of min-entropy \(\ge H_\infty (X_1,X_2)-\log (1/\epsilon )\), one with \(H_\infty (\hat Y_2\mid \hat Y_1=x)\ge a\) throughout, the other with it \({\lt}a\) throughout.
Split \(\mathrm{Supp}(X_1)\) by whether \(H_\infty (X_2\mid X_1=x)\ge a\), and condition \(X\) on each part. If the split probability \(p\in [\epsilon ,1-\epsilon ]\), each conditional loses \(\le \log (1/\epsilon )\) min-entropy and \((Y_1,Y_2)=(X_1,X_2)\) works; otherwise the heavy part alone is \(\epsilon \)-close and has enough min-entropy.
From a permutation conductor \(\langle E_1,C_1\rangle \), a buffer conductor \(\langle E_2,C_2\rangle \), and a lossless conductor \(E_3\), build \(E\) by: \((y_2,z_2)=\langle E_2,C_2\rangle (x_2,r_2)\); \((y_1,z_1)=\langle E_1,C_1\rangle (x_1,y_2)\); \(y_3=E_3(z_1z_2,r_3)\); output \(y_1y_3\).
With \(a=1000\log (1/\epsilon )\), \(d=2a\): \(\langle E_1,C_1\rangle \) an \((n-30a,6a,\epsilon )\)-permutation conductor, \(\langle E_2,C_2\rangle \) a \((14a,0,\epsilon )\)-buffer conductor, \(E_3\) a \((15a,a,\epsilon )\)-lossless conductor.
\(E:\{ 0,1\} ^n\times \{ 0,1\} ^{2a}\to \{ 0,1\} ^{n-3a}\) is an \((n-30a,2a,4\epsilon )\)-lossless conductor.
Ignoring \(\ell _1\)-errors first: by Lemma 181 treat the two extreme cases of \(H_\infty (X_2\mid X_1)\), in each obtaining \(H_\infty (Y_1)\ge k-14a\). Conservation of entropy by the permutation and buffer conductors gives \(H_\infty (Y_1,Z_1,Z_2)=k+a\), so \(H_\infty (Z_1,Z_2\mid Y_1=y_1)\le 15a\) and \(E_3\) conducts \(a\) more bits into \(Y_3\), yielding \(H_\infty (Y_1,Y_3)=k+2a\). Explicitness of \(E_1\) uses Proposition 51 (\(H_\infty \le H_2\le 2H_\infty \)). The four \(\ell _1\)-errors add to \(4\epsilon \).
For any \(\epsilon {\gt}0\) and \(M\le N\) there is an explicit family of left \(D\)-regular bipartite \((\Omega (\epsilon M/D),\epsilon )\)-lossless expanders with \(D\le (N/\epsilon M)^c\).
For \(\delta {\gt}0\) and large \(d\), explicitly construct \((n,d)\)-graphs with \(\Psi _V(G,\epsilon n)\ge d-2-\delta \).