TY - GEN
T1 - Dimension expanders via rank condensers
AU - Forbes, Michael A.
AU - Guruswami, Venkatesan
N1 - Publisher Copyright:
© Michael A. Forbes and Venkatesan Guruswami.
PY - 2015/8/1
Y1 - 2015/8/1
N2 - 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, two-source rank condensers, and rank-metric codes. In particular, with the recent construction of near-optimal subspace designs by Guruswami and Kopparty [12] as a starting point, we construct good (seeded) rank condensers (both lossless and lossy versions), which are a small collection of linear maps Fn → Ft for t ∗ n such that for every subset of Fn 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 O(1) explicit linear maps Ai: Fn → Fn such that for any subspace V ⊆ Fn of dimension at most n/2, dim(Σi Ai(V) ∗ (1 +Ω (1)) dim(V). Previous constructions of such constant-degree 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 two-source 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 rank-metric 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Ω(1)) rank. When the sources have O(1) rank, combining this with an "inner condenser" found by brute-force leads to a two-source rank condenser with output length nearly matching the probabilistic constructions.
AB - 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, two-source rank condensers, and rank-metric codes. In particular, with the recent construction of near-optimal subspace designs by Guruswami and Kopparty [12] as a starting point, we construct good (seeded) rank condensers (both lossless and lossy versions), which are a small collection of linear maps Fn → Ft for t ∗ n such that for every subset of Fn 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 O(1) explicit linear maps Ai: Fn → Fn such that for any subspace V ⊆ Fn of dimension at most n/2, dim(Σi Ai(V) ∗ (1 +Ω (1)) dim(V). Previous constructions of such constant-degree 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 two-source 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 rank-metric 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Ω(1)) rank. When the sources have O(1) rank, combining this with an "inner condenser" found by brute-force leads to a two-source rank condenser with output length nearly matching the probabilistic constructions.
KW - Dimension expanders
KW - Rank condensers
KW - Rank-metric codes
KW - Subspace designs
KW - Wronskians
UR - http://www.scopus.com/inward/record.url?scp=84958520640&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958520640&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX-RANDOM.2015.800
DO - 10.4230/LIPIcs.APPROX-RANDOM.2015.800
M3 - Conference contribution
AN - SCOPUS:84958520640
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 800
EP - 814
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015
A2 - Garg, Naveen
A2 - Jansen, Klaus
A2 - Rao, Anup
A2 - Rolim, Jose D. P.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015
Y2 - 24 August 2015 through 26 August 2015
ER -