The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


                            Computer Science Seminar

                                 Omer Reingold
                                  AT&T and IAS


                                 will speak on


                   Entropy Waves, The Zig-Zag Graph Product,
                and New Constant-Degree Expanders and Extractors

Abstract:
The main contribution of this work is a new type of graph product, which we
call the zig-zag product. Taking a product of a large graph with a small graph,
the resulting graph inherits (roughly) the size of the large one, the degree of
the small one, and the expansion properties of both!  Iteration yields simple
explicit constructions of constant-degree expanders of every size, from one
constant size expander.

A variant of this product can be applied to extractors, giving the first
explicit extractors whose degree depends polynomially on only the entropy
deficiency of the source and that extract almost all the entropy of high
min-entropy sources. These high min-entropy extractors have several interesting
applications, including the first constant-degree explicit expanders which beat
the eigenvalue bound.

Joint work with Salil Vadhan and Avi Wigderson.





                      The lecture will take place in the 
                     Lecture Hall, Room 1, Ziskind Building
                            on Monday, June 12, 2000
                                    at 14:30