Guruswami, Venkatesan ;
Resch, Nicolas ;
Xing, Chaoping
Lossless Dimension Expanders via Linearized Polynomials and Subspace Designs
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 nontrivial 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 listdecoding in the rankmetric. Our approach yields the following:
 Lossless expansion over large fields; more precisely beta >= (1epsilon)d and eta >= (1epsilon)/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 nontrivial 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.
BibTeX  Entry
@InProceedings{guruswami_et_al:LIPIcs:2018:8885,
author = {Venkatesan Guruswami and Nicolas Resch and Chaoping Xing},
title = {{Lossless Dimension Expanders via Linearized Polynomials and Subspace Designs}},
booktitle = {33rd Computational Complexity Conference (CCC 2018)},
pages = {4:14:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770699},
ISSN = {18688969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8885},
URN = {urn:nbn:de:0030drops88859},
doi = {10.4230/LIPIcs.CCC.2018.4},
annote = {Keywords: Algebraic constructions, coding theory, linear algebra, listdecoding, polynomial method, pseudorandomness}
}
2018
Keywords: 

Algebraic constructions, coding theory, linear algebra, listdecoding, polynomial method, pseudorandomness 
Seminar: 

33rd Computational Complexity Conference (CCC 2018)

Issue date: 

2018 
Date of publication: 

2018 