1 The magical mystery tour
For words \(u,v\in \Sigma ^n\) over an alphabet \(\Sigma \), the Hamming distance \(d_H(u,v)\) is the number of coordinates \(i\) with \(u_i\neq v_i\).
Let \(G=(L\cup R,E)\) be a bipartite graph. There is a matching saturating \(L\) iff \(|\Gamma (S)|\ge |S|\) for every \(S\subseteq L\).
For finite events \(A_1,\dots ,A_m\), \(\Pr [\bigcup _i A_i]\le \sum _i\Pr [A_i]\).
For integers \(1\le k\le n\), \(\binom nk\le (en/k)^k\).
If \(Z\sim \mathrm{Binomial}(N,p)\) then for \(0{\lt}\Delta {\lt}1\), \(\Pr [|Z-\mathbb {E}Z|\ge \Delta \mathbb {E}Z]{\lt}2\exp (-Np\Delta ^2/3)\).
Let \(A\) be an \(n\times n\) matrix over a field \(\mathcal F\). What is the least number of gates in an arithmetic circuit computing \(x\mapsto Ax\), where each gate has two inputs \(x,y\), two field coefficients \(a,b\), and output \(ax+by\)?
A matrix \(A\) is super regular if every square submatrix of \(A\) has full rank.
Let \(G=(V,E)\) and let \(I,O\subseteq V\) each have \(n\) vertices (inputs and outputs). \(G\) is a super concentrator if for every \(k\) and every \(S\subseteq I\), \(T\subseteq O\) with \(|S|=|T|=k\) there are \(k\) vertex-disjoint paths from \(S\) to \(T\).
Alice sends a \(k\)-bit message to Bob over a channel that may flip a fraction \(p\) of bits. What is the smallest \(n\) so that Bob can always recover the message?
For a code \(C\subseteq \{ 0,1\} ^n\), the rate and (normalized) distance are \(R=\frac{\log _2|C|}{n}\) and \(\delta =\frac{\min _{c_1\neq c_2\in C}d_H(c_1,c_2)}{n}\).
Do there exist arbitrarily large codes \(\{ C_k\} \), \(|C_k|=2^k\), with \(R(C_k)\ge R_0\) and \(\delta (C_k)\ge \delta _0\) for absolute constants \(R_0,\delta _0{\gt}0\), that are explicit and efficiently encodable/decodable?
\(\mathcal L\subseteq \{ 0,1\} ^*\) is in \(\mathbf{RP}\) if a randomized polynomial-time \(A\) satisfies: \(x\in \mathcal L\Rightarrow A(x,r)=1\) for all \(r\); \(x\notin \mathcal L\Rightarrow \Pr _r[A(x,r)=1]{\lt}1\) (fixed below \(1/16\)), with \(r\) uniform of length \(k=\mathrm{poly}(|x|)\).
Given a one-sided-error randomized membership algorithm for \(\mathcal L\), how many random bits suffice to reduce the error to \(\le \epsilon \) on every input?
A bipartite graph \(G=(L,R,E)\) with \(|L|=n\), \(|R|=m\), every left vertex of degree \(d\), and neighbourhood map \(\Gamma \), is an \((n,m;d)\)-magical graph if: (1) \(|\Gamma (S)|\ge \tfrac {5d}8|S|\) for \(|S|\le \tfrac n{10d}\); and (2) \(|\Gamma (S)|\ge |S|\) for \(\tfrac n{10d}{\lt}|S|\le \tfrac n2\).
There is \(n_0\) so that for every \(d\ge 32\), \(n\ge n_0\), \(m\ge 3n/4\), an \((n,m;d)\)-magical graph exists.
Let \(G\) be random bipartite, each left vertex joined to a uniform \(d\)-set on the right. Property (1): for \(S\), \(s=|S|\le \tfrac n{10d}\) and \(T\subseteq R\), \(t{\lt}\tfrac {5ds}8\), let \(X_{S,T}\) indicate all edges from \(S\) land in \(T\); \(\Pr [X_{S,T}=1]=(t/m)^{sd}\). By the union bound and \(\binom nk\le (en/k)^k\),
the \(s\)-th term being \(\le 20^{-s}\) for \(d\ge 32\). Property (2): for \(\tfrac n{10d}{\lt}s\le \tfrac n2\), \(t{\lt}s\), with \(Y_{S,T}\) the analogue, \(\Pr [\sum Y_{S,T}{\gt}0]\le \sum _s\binom ns\binom ms(s/m)^{sd} \le \sum _s[(ne/s)(me/s)(s/m)^d]^s{\lt}\tfrac 1{10}\), each bracket \(\le 10^{-4}\). The total failure probability is \({\lt}1\), so a magical (indeed most) graph exists.
In an \((n,3n/4;d)\)-magical graph, \(|\Gamma (S)|\ge |S|\) for every \(S\subseteq L\) with \(|S|\le \tfrac n2\), so by Hall’s theorem there is a matching saturating any such \(S\).
Property (1) gives \(|\Gamma (S)|\ge \tfrac {5d}8|S|\ge |S|\) for \(|S|\le \tfrac n{10d}\); property (2) gives \(|\Gamma (S)|\ge |S|\) for \(\tfrac n{10d}{\lt}|S|\le \tfrac n2\). Thus Hall’s condition holds for all such \(S\).
In an \((n,3n/4;d)\)-magical graph, every nonempty \(S\subseteq L\) with \(|S|\le \tfrac n{10d}\) has a vertex \(u\in R\) with \(|\Gamma (u)\cap S|=1\).
The number of edges between \(S\) and \(\Gamma (S)\) is \(d|S|\). By property (1) \(|\Gamma (S)|\ge \tfrac {5d}8|S|\), so the average number of \(S\)-neighbours of a vertex of \(\Gamma (S)\) is \(\le 8/5{\lt}2\); since each has \(\ge 1\), some has exactly one.
There exist super concentrators with \(n\) inputs, \(n\) outputs and \(O(n)\) edges.
Recursively: for \(n{\lt}n_0\) use the complete bipartite graph (\(n^2\) edges). For \(n\ge n_0\) build \(C'\) from two copies \(G_1,G_2\) of an \((n,3n/4;d)\)-magical graph, a super concentrator \(C\) on \(R_1,R_2\) (size \(3n/4\), by induction), and a perfect matching between \(L_1,L_2\); inputs/outputs are \(L_1,L_2\). For \(|S|=|T|=k\le n/2\), Lemma 16 and Hall give matchings of \(S,T\) into \(R_1,R_2\); their images are joined by \(k\) disjoint paths in \(C\). For \(k{\gt}n/2\), route \(k-n/2\) pairs directly through the matching and reduce to \(k\le n/2\). The edge recursion \(e(n)\le 2nd+n+e(3n/4)\) (\(n{\gt}n_0\)), \(e(n)=n^2\) (\(n\le n_0\)) solves to \(e(n)\le Kn\).
An \((n,3n/4;d)\)-magical graph yields a linear code \(C\subseteq \{ 0,1\} ^n\) with rate \(R\ge \tfrac 14\) and normalized distance \(\delta \ge \tfrac 1{10d}\).
Let \(A\) be the \(|R|\times |L|\) bipartite adjacency matrix over \(\mathrm{GF}(2)\) and \(C=\{ x:Ax=0\} \). Then \(\dim C\ge n-|R|=n/4\), so \(R\ge \tfrac 14\). Since \(C\) is linear, its distance is the minimum weight of a nonzero codeword; if a nonzero \(x\) had support \(S\) with \(|S|{\lt}\tfrac n{10d}\), then by Lemma 17 some coordinate of \(Ax\) is \(1\), so \(x\notin C\). Hence \(\delta \ge \tfrac 1{10d}\).
For \(\mathcal L\in \mathbf{RP}\) with one-sided-error algorithm \(f\) using \(k\) bits, \(n=2^k\), failing on \(B\) with \(|B|\le n/16\): for every \(d\) there is an algorithm evaluating \(f\) exactly \(d\) times, using only the \(k\) random bits, with error \(\le \tfrac 1{10d}\).
Use an \((n,n;d)\)-magical graph \(G=(L,R,E)\), \(R\) identified with \(\{ 0,1\} ^k\). Sample \(r\in L\), let \(r_1,\dots ,r_d\) be its neighbours, output \(\bigwedge _i f(x,r_i)\). For \(x\in \mathcal L\) this is always \(1\). For \(x\notin \mathcal L\) failure means all \(r_i\in B\); let \(S=\{ r:\Gamma (r)\subseteq B\} \). If \(|S|{\gt}\tfrac n{10d}\) then by property (1) \(|B|\ge |\Gamma (S)|{\gt}\tfrac {5d}8\cdot \tfrac n{10d}=\tfrac n{16}\), contradiction. So \(|S|\le \tfrac n{10d}\) and \(\Pr [r\in S]\le \tfrac 1{10d}\).