-----------------------------------------------------------------------
                   B O S T O N   U N I V E R S I T Y
                      Computer Science Department
                          C O L L O Q U I U M
                      Wednesday, March 13, 3:00 PM 
                       (Coffee served at 2:45 PM)
                         Seminar Room / MCS 135

          Randomness Conductors and Constant-Degree Expansion 
                       Beyond the Degree/2 Barrier

                             Salil Vadhan
                          Harvard University

                              Abstract

The main concrete contribution of this work is the first
explicit construction of constant-degree "lossless" expanders. In
these graphs, the expansion factor is almost as large as possible:
(1-eps)*D, where D is the degree and eps is an arbitrarily small
constant. Such graphs are known to have many applications, e.g. in
constructing networks that can implement fast distributed, routing
algorithms, expander-based linear codes, various storage schemes, and
hard tautologies for various proof systems.  The best previous
explicit constructions gave expansion factor D/2, which is too weak
for the above applications. The D/2 bound was obtained via the
eigenvalue method, and it was known that that method cannot give better
bounds.

The main abstract contribution of this paper is the introduction and
initial study of "randomness conductors", a notion which generalizes
expanders, extractors, condensers and other similar objects. In all
these functions, certain guarantees on the input "entropy" are
converted to guarantees on the output "entropy".  For historical
reasons, specific objects used specific guarantees of different
flavors.  We show that the flexibility afforded by the conductor
definition leads to interesting combinations of these objects, and to
better constructions such as those above.

The main technical tool in these constructions is a natural
generalization to conductors of the zig-zag graph product,
previously defined for expanders and extractors.

Joint work with Michael Capalbo, Omer Reingold, and Avi Wigderson.


Host: Leonid Reyzin
-------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
-------------------------------------------------------------------------