Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-135 | 10th December 2009 21:35

Monotone expanders - constructions and applications


Authors: Zeev Dvir, Avi Wigderson
Publication: 11th December 2009 08:07
Downloads: 3651


The main purpose of this work is to formally define monotone expanders and motivate their study with (known and new) connections to other graphs and to several computational and pseudorandomness problems. In particular we explain how monotone expanders of constant degree lead to:
(1) Constant degree dimension expanders in finite fields, resolving a question of [BISW].
(2) $O(1)$-page and $O(1)$-pushdown expanders, resolving a question of [GKS86], and leading to tight lower bounds on simulation time for certain Turing Machines.

Bourgain [Bou09] gave recently an ingenious construction of such constant degree monotone expanders. The first application (1) above follows from a reduction in [DS07]. We give a short exposition of both construction and reduction.

The new contributions of this paper are simple. First, we explain the observation leading to the second application (2) above, and some of its consequences. Second, we observe that a variant of the zig-zag graph product preserves monotonicity, and use it to give a simple alternative construction of monotone expanders, with near-constant degree.

ISSN 1433-8092 | Imprint