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}


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}.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Course, Workshop lecture and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s