[METRIC 2011] Zeev Dvir

Nicolas Schabanel
19
95 vues
  • Infos
  • Exporter
  • Ajouter à
  • Playlists
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.

0 commentaire