Volume 6 (2010)
Article 12 pp. 291-308
[Research Survey]

Monotone Expanders: Constructions and Applications

Received: February 4, 2010

Published: December 30, 2010

Published: December 30, 2010

**Keywords:**expander, zig-zag, k-page graphs, pushdown graphs

**ACM Classification:**F.1.3, G.2.2

**AMS Classification:**68Q15, 68R10

**Abstract:**
[Plain Text Version]

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:

- Constant degree dimension expanders in finite fields, resolving a question of Barak, Impagliazzo, Shpilka, and Wigderson (2004);
- O(1)-page and O(1)-pushdown expanders, resolving a question of Galil, Kannan, and Szemerédi (1986) and leading to tight lower bounds on simulation time for certain Turing Machines.