Computer Science/Discrete Mathematics Seminar II | |

Topic: | Dimension expanders via rank condensers |

Speaker: | Michael Forbes |

Affiliation: | Member, School of Mathematics |

Date: | Tuesday, February 3 |

Time/Room: | 10:30am - 12:30pm/S-101 |

Video Link: | http://video.ias.edu/csdm/2015/0203-MichaelForbes |

Expander graphs are sparse graphs with good connectivity properties and they have become ubiquitous in theoretical computer science. Dimension expanders are a linear-algebraic variant where we ask for a constant number of linear maps that expand subspaces of a vector space (instead of subsets of vertices). After their definition 10 years ago by Barak, Impagliazzo, Shpilka and Wigderson there are now two constructions of constant-degree dimension expanders, both of which suggest dimension expanders are more complicated than expander graphs. In this work, we give a new construction of constant-degree dimension expanders (over large fields) which is quite simple. It follows from an emerging theory of linear-algebraic pseudorandomness where the rank of a subspace plays the role of the min-entropy of a random variable. In particular, we use the recent near-optimal construction of subspace designs by Guruswami and Kopparty (based on Wronskians) to construct a near optimal "lossy rank condenser". This condenser, in addition to a tensoring operation, yields the desired dimension expanders. Joint work with Venkatesan Guruswami