Randomness Conductors and Constant-Degree Lossless Expanders
Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson
Abstract
The main concrete result of this paper 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. The best previous explicit constructions
gave expansion factor D/2, which is too weak for many applications. The
D/2 bound was obtained via the eigenvalue method, and is 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
extractors, expanders, condensers and other similar objects. In all these
functions, certain guarantee on the input "entropy" is converted to a guarantee
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.
Versions
-
Preliminary version, November 2001. (has some proofs omitted from
version below, but contains typos)
[
postscript
] [
compressed postscript ]
-
In Proceedings of the 34th Annual ACM Symposium on Theory of Computing,
Montreal,
Canada, May 19-21, 2002. Joint session with 17th Conference on
Computational Complexity.
[
postscript ] [
compressed postscript ]
[ back to
Salil Vadhan's research interests ]