"Dimension Expanders via Rank Condensers"
Michael Forbes
(MIT)
Monday, December 8st, 2014, 2:00 pm
EBU3B, Room 4258
Abstract:
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