Haifa University - Dept. of CS Theory Seminar

Speaker : Amnon Ta-Shma, Tel-Aviv University.

Title: "A combinatorial construction of almost-Ramanujan graphs using the zig-zag product ".

Date: Thursday, July 3.

Place: Haifa U. Education Building, room 566.

Time: 12:15 - 13:30

Abstract:

Reingold, Vadhan and Wigderson introduced the graph zig-zag product. This
product combines a large graph and a

small graph into one graph, such that the resulting graph inherits its size from
the large graph, its degree from the small graph and

its spectral gap from both. Using this product they gave the first
fully-explicit combinatorial construction of expander graphs. They

showed how to construct D--regular graphs having spectral gap 1-O(D^{-1/3}). In
the same paper, they posed the open

problem of whether a similar graph product could be used to achieve the
almost-optimal spectral gap 1-O(D^{-1/2}).

In this paper we propose a generalization of the zig-zag product that combines a
large graph and several small graphs. The new

product gives a better relation between the degree and the spectral gap of the
resulting graph. We use the new product to

give a fully-explicit combinatorial construction of D--regular graphs having
spectral gap $1-D^{-1/2 + o(1)}$.

Joint work with Avraham Ben-Aroya