## 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, 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 → 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 O(1) explicit linear maps Ai: F^{n} → F^{n} such that for any subspace V ⊆ F^{n} of dimension at most n/2, dim(Σ_{i} A_{i}(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.

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015 |

Editors | Naveen Garg, Klaus Jansen, Anup Rao, Jose D. P. Rolim |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Pages | 800-814 |

Number of pages | 15 |

ISBN (Electronic) | 9783939897897 |

DOIs | |

State | Published - Aug 1 2015 |

Externally published | Yes |

Event | 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015 - Princeton, United States Duration: Aug 24 2015 → Aug 26 2015 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 40 |

ISSN (Print) | 1868-8969 |

### Other

Other | 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015 |
---|---|

Country/Territory | United States |

City | Princeton |

Period | 8/24/15 → 8/26/15 |

## Keywords

- Dimension expanders
- Rank condensers
- Rank-metric codes
- Subspace designs
- Wronskians

## ASJC Scopus subject areas

- Software