文章基本信息

标题：Dimension Expanders via Rank Condensers
本地全文：下载
作者：Michael A. Forbes ; Venkatesan Guruswami
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：40
页码：800-814
DOI：10.4230/LIPIcs.APPROX-RANDOM.2015.800
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 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<
关键词：dimension expanders; rank condensers; rank-metric codes; subspace designs; Wronskians