Volume 6 (2010) Article 12 pp. 291-308 [Research Survey]
Monotone Expanders: Constructions and Applications
by
Published: December 30, 2010
[PDF (242K)]    [PS (866K)]    [PS.GZ (253K)]
[Source ZIP]
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:
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 Szemerédi (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.