License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2018.4
URN: urn:nbn:de:0030-drops-88859
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8885/
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 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.
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:1--4:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-069-9},
ISSN = {1868-8969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8885},
URN = {urn:nbn:de:0030-drops-88859},
doi = {10.4230/LIPIcs.CCC.2018.4},
annote = {Keywords: Algebraic constructions, coding theory, linear algebra, list-decoding, polynomial method, pseudorandomness}
}
|
Keywords: |
|
Algebraic constructions, coding theory, linear algebra, list-decoding, polynomial method, pseudorandomness |
|
Collection: |
|
33rd Computational Complexity Conference (CCC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.06.2018 |
