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 method. Breaking the D/2 barrier was not only a theoretical challenge. This level of expansion is vital for several interesting applications like explicit and efficient error-correcting codes, networks suitable for distributed routing, distributed memory management, fault tolerance and more.

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