Expanders, Property Testing and the PCP theorem

Schedule for rest of the semester

Posted in annoucements by atri on October 23, 2008

Below is the planned schedule for the rest of the semester (it is your responsibility to be aware of the meeting times even if we forget to mention them in the previous class):

  • Oct 24 (Fri): 10am-noon. Property Testing: Lecture 1 (Atri)
  • Oct 27 (Mon): No class.
  • Oct 31 (Fri): 11am-noon. Theory seminar (Muthu Venkitsubramaniam)
  • Nov 3 (Mon): 10am-noon. Property Testing: Lecture 2 (Atri)
  • Nov 7 (Fri): 10am-noon. Property Testing: Lecture 3 (Atri)
  • Nov 10 (Mon): 10am-noon. Property Testing: Lecture 4 (Atri)
  • Nov 14 (Fri): No class.
  • Nov 17 (Mon): 10:30am-noon. Student Presentation 1 (Yang)
  • Nov 21 (Fri): 10:30am-noon. Student Presentation 2 (Nathan)
  • Nov 24 (Mon): 10:30am-noon. Student Presentation 3 (Swapnoneel)
  • Nov 27 (Fri): No class.
  • Dec 1 (Mon): 10:30am-noon. Student Presentation 4 (Steve)
  • Dec 5 (Fri): 10:30am-noon. Student Presentation 5 (Than) Last meeting.

Some suggestions for presentations (all of which have to be on property testing) are now online. We very strongly recommend that you start looking at the papers ASAP and make your choice soon. (Almost all of the papers in the list will most probably turn out to be a harder read than most of the stuff you guys presented in the first half of the seminar.)

leave a comment

Lecture 9: Zig-Zag Product

Posted in lectures by NQH on October 9, 2008

We talked about the zig-zag product today. Let G, H be an (n,m,\alpha)-spectral expander and an (m,d,\beta)-spectral expander, respectively. Let’s use \star to denote the zig-zag product. The graph G\star H is an (mn, d^2, f(\alpha,\beta))-spectral expander where f(\alpha,\beta)<1 if \alpha<1 and \beta<1. Moreover, f(\alpha,\beta) \leq \alpha+\beta+\beta^2. For better upper-bounds on f(\alpha,\beta), see the original zig-zag product paper. For a recent new construction of expanders, see this paper. Perhaps one of you can present this paper.

For each vertex u \in V(G), label all edges incident to u arbitrarily by e_u^1, \dots, e_u^m.  The product is defined as follows:

  • The graph G\star H has vertex set V = \{(u,i) \ | \ u\in V(G), i \in [m]=V(H)\}.
  • There is an edge from (u,i) to (v,j) iff there are k, l \in [m] such that ik \in E(H), e_u^k = e_v^l, and lj \in E{H}. It is not difficult to see that the product has mn vertices and degree d^2.

Let \mathbf{\hat A}, \mathbf{\hat B} be the normalized adjacency matrices of G, H, respectively. Define an mn \times mn matrix \mathbf P where p_{(u,k),(v,l)} = 1 iff e_u^k = e_v^l. Then, \mathbf P is a symmetric permutation matrix. Now, let \mathbf{\tilde B} = \mathbf I_n \otimes \mathbf{\hat B} (where \otimes denote the tensor product of two matrices). Then, it follows that \mathbf M = \mathbf{\tilde B P \tilde B} is the normalized adjacency matrix of the product graph G\star H. So,

f(\alpha,\beta) = \max_{\mathbf{x \perp u}} \frac{|\langle \mathbf{\tilde B P \tilde B x, x} \rangle|}{\langle x, x \rangle}

Fix a vector \mathbf{x \perp u} \in \mathbb R^{mn}. Define a “collection vector” C(\mathbf x) \in \mathbb R^n as follows: C(\mathbf x)_u = \frac 1 m \sum_{i\in [m]} x_{(u,i)}. So the uth entry of C(\mathbf x) is just the average over all entries x_{(u,i)} in the uth “cloud” of the vector \mathbf x. Also define

\mathbf x^{\|} := C(\mathbf x) \otimes \mathbf 1_m where \mathbf 1_m \in \mathbb R^m is the all-1 vector

\mathbf x^\perp = \mathbf x - \mathbf x^\|

Fix a vector \mathbf x \perp \mathbf u, we want to derive something like |\langle \mathbf{\tilde B P \tilde B x, x} \rangle| \leq f(\alpha, \beta) \langle \mathbf{x,x} \rangle. So, let’s start with the left hand side. Note that, since \mathbf x^\| is uniform on each “cloud”, we have \mathbf{\tilde Bx^\| = x^\|}.

|\langle \mathbf{\tilde B P \tilde B (x^\|+x^\perp), (x^\|+x^\perp)} \rangle| \leq |\langle \mathbf{Px^\|, x^\|} \rangle| + 2|\langle \mathbf{P\tilde B x^\perp, \tilde B x^\|} \rangle| + \|\mathbf{\tilde Bx^\perp} \|^2

Consider the last term. Since \mathbf x^\perp is anti-uniform on each “cloud” (i.e. the sum of \mathbf x^\perp’s coordinates on each cloud is zero), implying that \|\mathbf{\tilde Bx^\perp}\| \leq \beta \|\mathbf x^\perp\|.

We now bound the second term. Since \mathbf P is a permutation matrix, it does not changes a vector’s norm. We have

2|\langle \mathbf{P\tilde B x^\perp, \tilde B x^\|} \rangle| \leq 2\| \mathbf{P\tilde Bx^\perp}\| \|\mathbf{\tilde B x^\|}\| \leq 2\beta \|x^\perp\| \|x^\|\|

Finally, we bound the first term. Relatively straightforward computation leads to

\langle \mathbf{Px^\|, x^\|} \rangle = m \langle \mathbf{\hat A} C(\mathbf x), C(\mathbf x)\rangle \leq m\alpha \|C(\mathbf x)\|^2 = \alpha \|\mathbf x^\|\|^2.

Consequently,

|\langle \mathbf{\tilde B P \tilde B x, x} \rangle| \leq \alpha \|\mathbf x^\|\|^2 + 2\beta \|x^\perp\| \|x^\|\| + \beta^2 \|\mathbf x^\perp\|^2

Noting that \|\mathbf x\|^2 = \|\mathbf x^\|\|^2 + \|\mathbf x^\perp\|^2. It is easy to show that

|\langle \mathbf{\tilde B P \tilde B x, x} \rangle| \leq \max(\alpha+\beta, \beta+\beta^2)\|\mathbf x\|^2 \leq (\alpha+\beta+\beta^2)\|\mathbf x\|^2.

Now, suppose we start from a (d^4,d,1/5)-spectral expander H. Let G_1=H^2 and G_n = G_{n-1}^2 \star H. It is not difficult to prove by induction that G_n is a (d^{4n}, d^2, 2/5)-spectral expander.

The zig-zag construction can also be made strongly explicit.

leave a comment