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

Monotone Expanders: Constructions and Applications

by Zeev Dvir and Avi Wigderson

Received: February 4, 2010
Published: December 30, 2010

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.

DOI: 10.4086/toc.2010.v006a012

© 2010 Zeev Dvir and Avi Wigderson
Licensed under a Creative Commons Attribution License (CC-BY)