Dimension expanders via rank condensers

Dimension expanders via rank condensers - Micheal Forbes

Michael Forbes
Member, School of Mathematics
February 3, 2015
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