[METRIC 2011] Zeev Dvir

METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)
Workshop on Expanders and derandomization (March 21-25, 2011)
Mar 21, 16:30-17: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 < u' --> v < v'. It is not clear a priori if monotone expanders exist or not. This is partially due to the fact that the natural application of the probabilistic method does not work in this special case.

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.