Department of Computer Science Colloquium

Thursday April 4th, 2002 at 4:15pm

Upson Hall B17

**The
Zigzag Graph Product and Constant-Degree Lossless Expanders**

**Omer
Reingold
**

AT&T and IAS

Expanders
are graphs or networks that have a sparse number of edges, but nonetheless are
highly connected. Consider a network where every node is directly connected to
exactly D other nodes. The network is called an expander if every set S of some
K nodes can reach “many” other nodes in one hop. More specifically, we want
S to have AK neighbors for some constant A>1. Surprisingly, this
“innocent” definition has deep implications and addresses many fundamental
problems in computer science, on topics including network design, complexity
theory, derandomization, coding theory and cryptography.

We
present the first simple combinatorial construction of constant-degree
expanders. Furthermore, we give the first explicit construction of
constant-degree "lossless" expanders. In these graphs, the expansion
factor A is almost as large as possible: (1-e)D, where e is an arbitrarily small
constant. The best previous explicit constructions gave expansion factor D/2.
The D/2 bound was obtained via the eigenvalue method, and is known to be the
best possible using this

Our
constructions rely on a new type of graph product, which we call the zigzag
product. Taking a product of a large graph with a small graph, the resulting
graph inherits the size from the large one, the degree from the small one, and
the expansion properties from both. Iteration yields simple explicit
constructions of constant-degree expanders. Pushing this construction much
further produces our lossless expanders.

Based on a joint work with Salil Vadhan and Avi Wigderson (FOCS 2000) and a joint work with Michael Capalbo, Salil Vadhan and Avi Wigderson (to appear in STOC 2002).