Notes of Avi Wigderson’s lecture nr 2

1. More applications

1.1. Sorting networks

These are communication networks which are oblivious (do not make any decision based upon content). Input: ${n}$ real numbers. Output: the same, ordered.

Theorem 1 (Ajtai, Komlos, Szemerédi) There is an explicit sorting network of size ${n\log n}$.

Corollary 2 There is an explicit monotone Boolean formula for Majority

After a randomized existence proof of Valiant.

1.2. Deterministic error reduction

Assume algorithm makes mistakes with probability ${<1/3}$. Modify it so that probability of error gets smaller.

Trivial solution: repeat algorithm on same input ${k}$ times and take majority. Chernoff’s bound gives exponentially decaying error probability. This requires ${kn}$ random bits.

On the set ${\{ 0,1 \}^n}$ of input strings, put the edges of an expander. Then do ${k}$ steps of random walk on the resulting graph and take majority.

Theorem 3 (Ajtai, Komlos, Szemerédi) Same exponential decay with merely ${n+O(k)}$ random bit.

1.3. Metric embeddings

Bourgain showed that every ${n}$-point has a ${O(\log n)}$ embedding into ${L_2}$. This is sharp.

Theorem 4 (Linial, London, Rabinovich) Expanders, when embedded in ${L_2}$, incur distorsion at least ${\Omega(\log n)}$.

Proof: Convert spectral gap into a Poincaré inequality

$\displaystyle \begin{array}{rcl} (1-\lambda)\mathop{\mathbb E}_{x,y}|f(x)-f(y)|^2 \leq \mathop{\mathbb E}_{x\sim y}|f(x)-f(y)|^2 . \end{array}$

$\Box$

A coarse embedding of a metric space to ${L_2}$ has ${|f(x)-f(y)|}$ sandwiched between to functions of ${d(x,y)}$

Theorem 5 (Gromov) There exists a finitely presented group ${G}$ whose Cayley graph has not coarse embedding into ${L_2}$.

Proof: Contruct ${G}$ in such a way that its Cayley graph contains a sequence of larger and larger expander graphs. $\Box$

1.4. Non linear spectral gaps

Theorem 6 (Matousek) Expanders satisfy ${L_p}$-valued Poincaré inequality

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E}_{x,y}|f(x)-f(y)|_p^2 \leq \gamma\mathop{\mathbb E}_{x\sim y}|f(x)-f(y)|_p^2 . \end{array}$

See Mendel’s talk.

2. Constructions

2.1. Cayley graphs of finite groups

Which Cayley graphs are expanding ?

Examples by Margulis, Gaber-Galil, Alon-Milman, LPS, Nikolov, Kassabov,…

Mother example is Selberg’s congruence quotients of ${SL_2 ({\mathbb Z})}$. It gives rise to a strongly explicit expander : Takes ${O(n)}$ bits to describe a matrix in ${SL_2 (p)}$.

See Gamburd’s course.

2.2. Combinatorial construction: the zig-zag product

Given graphs ${G}$ and ${H}$, there zig-zag product is a graph ${G\otimes H}$ whose

• vertices come in clouds modelled on ${H}$, indexed by ${G}$;
• edges correspond to 3 steps walks: one step in cloud 1, one step between clouds, one step in cloud 2.

There is some freedom in the construction.

Theorem 7 (Reingold, Vadhan, Wigderson) If ${G}$ is an ${(n,m,\alpha)}$-graph and ${H}$ an ${(m,d,\beta)}$-graph, ${G\otimes H}$ is a ${(nm,d^2 ,\alpha+\beta)}$-graph.

Proof: Expansion implies that entropy of distribution increases under random walk. And conversely. Many choices of entropy work (see Mendel’s talk).

Random walk in ${G\otimes H}$ amounts to one step of random walk in ${H}$ (increase entropy, strictly if conditional entropy is far from maximum), then one step of random walk in ${G}$, (increase entropy, strictly if conditional entropy is far from maximum), then one step of random walk in ${H}$ (increase entropy, strictly if conditional entropy is far from maximum). If total entropy is not close to maximum, one of the conditional entropies is too. $\Box$

2.3. Iterative construction of expanders

Start with a constant size ${(d^4 ,d,\frac{1}{4})}$-graph ${H}$ (can be constructed by hand). Let ${G_1 =H^2}$, ${G_{k+1}=G_k^2 \otimes H}$. Then ${G_k}$ is a ${(d^{4k},d^2,\frac{1}{2})}$-graph. Indeed, squaring squares the spectral gap.

2.4. Consequences

• Isoperimetric inequalities beating eigenvalue bounds.
• New expanding Cayley graphs for non-simple groups [Meshulam, Wigderson]
• ${SL=L}$ [Reingold].

2.5. How to escape mazes

Theorem 8 (Aleliunas et al., 1980) On any connected regular graph, random walk will visit every vertex in ${n^2}$ steps with high probability.

Omer Reingold could derandomize this algorithm. The solution uses zig-zag products. Let ${G_1 =G}$ be the given graph. Form ${G_{k+1}=G_k^5 \otimes H}$. After a logarithmic number of steps, ${G_k}$ is an expander. Try all paths of length ${\log n}$. They will cover all vertices of ${G_k}$. Construction of ${G_{k+1}}$ from ${G_{k}}$ is local, it can be done in a bounded time and space, so describing neighbors in ${G_k}$ requires space at most ${\log n}$.

2.6. Semi-direct products of groups

Let ${A}$, ${B}$ be groups, let ${B}$ act on ${A}$ by automorphisms. Define multiplication

$\displaystyle \begin{array}{rcl} (a',b')(a,b)=(a'a^{b},b'b). \end{array}$

on ${A\times B}$.

Example 1 Let ${A={\mathbb Z}_2^m}$ and ${B:{\mathbb Z}_m}$ cyclically permuting coordinates. Then semi-direct product is wreath product ${{\mathbb Z}_2 \wr {\mathbb Z}_m}$.

Theorem 9 (Alon, Lubotzky, Wigderson) Semi-direct product of groups yields zig-zag product of Cayley graphs, provided generating set in ${A}$ is a single ${B}$-orbit.

Corollary 10 Expansion is not a group property, i.e. it depends on generating set.

Use ${B=SL-2 (p)}$ and ${A={\mathbb Z}_2^{p+1}}$.

Since Kassabov gave a better example: symmetric group ${\mathfrak{S}_n}$.