Abstract
An emerging theory of "linear algebraic pseudorandomness: aims to understand the linear algebraic analogs of fundamental Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets. In this work, we study and highlight the interrelationships between several such algebraic objects such as subspace designs, dimension expanders, seeded rank condensers, twosource rank condensers, and rankmetric codes. In particular, with the recent construction of nearoptimal subspace designs by Guruswami and Kopparty as a starting point, we construct good (seeded) rank condensers (both lossless and lossy versions), which are a small collection of linear maps F^n to F^t for t<<n such that for every subset of F^n of small rank, its rank is preserved (up to a constant factor in the lossy case) by at least one of the maps.
We then compose a tensoring operation with our lossy rank condenser to construct constantdegree dimension expanders over polynomially large fields. That is, we give a constant number of explicit linear maps A_i from F^n to F^n such that for any subspace V of F^n of dimension at most n/2, the dimension of the span of the A_i(V) is at least (1+Omega(1)) times the dimension of V. Previous constructions of such constantdegree dimension expanders were based on Kazhdan's property T (for the case when F has characteristic zero) or monotone expanders (for every field F); in either case the construction was harder than that of usual vertex expanders. Our construction, on the other hand, is simpler.
For twosource rank condensers, we observe that the lossless variant (where the output rank is the product of the ranks of the two sources) is equivalent to the notion of a linear rankmetric code. For the lossy case, using our seeded rank condensers, we give a reduction of the general problem to the case when the sources have high (n^Omega(1)) rank. When the sources have constant rank, combining this with an "inner condenser" found by bruteforce leads to a twosource rank condenser with output length nearly matching the probabilistic constructions.
BibTeX  Entry
@InProceedings{forbes_et_al:LIPIcs:2015:5337,
author = {Michael A. Forbes and Venkatesan Guruswami},
title = {{Dimension Expanders via Rank Condensers}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {800814},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897897},
ISSN = {18688969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5337},
URN = {urn:nbn:de:0030drops53379},
doi = {10.4230/LIPIcs.APPROXRANDOM.2015.800},
annote = {Keywords: dimension expanders, rank condensers, rankmetric codes, subspace designs, Wronskians}
}
Keywords: 

dimension expanders, rank condensers, rankmetric codes, subspace designs, Wronskians 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) 
Issue Date: 

2015 
Date of publication: 

13.08.2015 