Advertising Console

    [METRIC 2011] Zeev Dvir

    Nicolas Schabanel

    par Nicolas Schabanel

    104 vues
    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 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.