Please use this identifier to cite or link to this item:
Title: Lossless dimension expanders via linearized polynomials and subspace designs
Authors: Guruswami, Venkatesan
Resch, Nicolas
Xing, Chaoping
Keywords: Coding Theory
Algebraic Constructions
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.
DOI: 10.4230/LIPIcs.CCC.2018.4
Schools: School of Physical and Mathematical Sciences 
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

Citations 50

Updated on Sep 16, 2023

Web of ScienceTM
Citations 50

Updated on Sep 22, 2023

Page view(s)

Updated on Sep 23, 2023

Download(s) 50

Updated on Sep 23, 2023

Google ScholarTM




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