## Schedule for rest of the semester

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.
- 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.
**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.)

## Lecture 9: Zig-Zag Product

We talked about the zig-zag product today. Let be an -spectral expander and an -spectral expander, respectively. Let’s use to denote the zig-zag product. The graph is an -spectral expander where if and . Moreover, . For better upper-bounds on , 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 , label all edges incident to arbitrarily by . The product is defined as follows:

- The graph has vertex set .
- There is an edge from to iff there are such that , , and . It is not difficult to see that the product has vertices and degree .

Let be the normalized adjacency matrices of , respectively. Define an matrix where iff . Then, is a symmetric permutation matrix. Now, let (where denote the tensor product of two matrices). Then, it follows that is the normalized adjacency matrix of the product graph . So,

Fix a vector . Define a “collection vector” as follows: . So the th entry of is just the average over all entries in the th “cloud” of the vector . Also define

where is the all-1 vector

Fix a vector , we want to derive something like . So, let’s start with the left hand side. Note that, since is uniform on each “cloud”, we have .

Consider the last term. Since is anti-uniform on each “cloud” (i.e. the sum of ‘s coordinates on each cloud is zero), implying that .

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

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

.

Consequently,

Noting that . It is easy to show that

.

Now, suppose we start from a -spectral expander . Let and . It is not difficult to prove by induction that is a -spectral expander.

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

leave a comment