Dimension expanders via rank condensers

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