METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)
Workshop on Expanders and derandomization (March 21-25, 2011)
Mar 21, 16:30
- Zeev Dvir (Princeton U.)
Monotone expanders - constructions and applications
A Monotone Expander is an expander graph which can be decomposed into a union of a constant number of monotone matchings, under some fixed ordering of the vertices. A matching is monotone if every two edges (u,v) and (u',v') in it satisfy u v
The first construction of monotone expanders with *logarithmic* degree was given in [D. Shpilka 05] and was motivated by an application to 'Dimension Expanders' (an algebraic analog of expander graphs). Later, in [Bourgain 09], a rather involved construction with constant degree was given. A simple construction with 'log-star' degree, based on the Zig-Zag product, was given in [D. Wigderson 10], together with other applications coming from the study of Turing Machines.
This talk will survey the above results in a high-level way.