Theory of Computing
-------------------
Title     : Monotone Expanders: Constructions and Applications
Authors   : Zeev Dvir and Avi Wigderson
Volume    : 6
Number    : 12
Pages     : 291-308
URL       : https://theoryofcomputing.org/articles/v006a012

Abstract
--------

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 Barak, Impagliazzo, Shpilka, and Wigderson (2004);

2. O(1)-page and O(1)-pushdown expanders, resolving a question of
Galil, Kannan, and Szemeredi (1986) and leading to tight lower 
bounds on simulation time for certain Turing Machines.

Recently, Bourgain (2009) gave a rather involved construction of
such constant degree monotone expanders. The first application (1)
above follows from a reduction due to Dvir and Shpilka (2007).
We sketch Bourgain's construction and describe the 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.