Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/89333
Title: Lossless dimension expanders via linearized polynomials and subspace designs
Authors: Guruswami, Venkatesan
Resch, Nicolas
Xing, Chaoping
Keywords: Coding Theory
Algebraic Constructions
DRNTU::Science::Mathematics
Issue Date: 2018
Source: Guruswami, V., Resch, N., & Xing, C. (2018). Lossless dimension expanders via linearized polynomials and subspace designs. Leibniz International Proceedings in Informatics, 102, 4-. doi:10.4230/LIPIcs.CCC.2018.4
Series/Report no.: Leibniz International Proceedings in Informatics
Abstract: For a vector space F^n over a field F, an (eta,beta)-dimension expander of degree d is a collection of d linear maps Gamma_j : F^n -> F^n such that for every subspace U of F^n of dimension at most eta n, the image of U under all the maps, sum_{j=1}^d Gamma_j(U), has dimension at least beta dim(U). Over a finite field, a random collection of d = O(1) maps Gamma_j offers excellent "lossless" expansion whp: beta ~~ d for eta >= Omega(1/d). When it comes to a family of explicit constructions (for growing n), however, achieving even modest expansion factor beta = 1+epsilon with constant degree is a non-trivial goal. We present an explicit construction of dimension expanders over finite fields based on linearized polynomials and subspace designs, drawing inspiration from recent progress on list-decoding in the rank-metric. Our approach yields the following: - Lossless expansion over large fields; more precisely beta >= (1-epsilon)d and eta >= (1-epsilon)/d with d = O_epsilon(1), when |F| >= Omega(n). - Optimal up to constant factors expansion over fields of arbitrarily small polynomial size; more precisely beta >= Omega(delta d) and eta >= Omega(1/(delta d)) with d=O_delta(1), when |F| >= n^{delta}. Previously, an approach reducing to monotone expanders (a form of vertex expansion that is highly non-trivial to establish) gave (Omega(1),1+Omega(1))-dimension expanders of constant degree over all fields. An approach based on "rank condensing via subspace designs" led to dimension expanders with beta >rsim sqrt{d} over large fields. Ours is the first construction to achieve lossless dimension expansion, or even expansion proportional to the degree.
URI: https://hdl.handle.net/10356/89333
http://hdl.handle.net/10220/46214
DOI: http://dx.doi.org/10.4230/LIPIcs.CCC.2018.4
Rights: © 2018 Venkatesan Guruswami, Nicolas Resch, and Chaoping Xing; licensed under Creative Commons License CC-BY.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
Lossless dimension expanders via linearized polynomials and subspace designs.pdf569.32 kBAdobe PDFThumbnail
View/Open

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.