Affordable Access

deepdyve-link
Publisher Website

Lossless dimension expanders via linearized polynomials and subspace designs

Authors
  • Guruswami, V. (Venkatesan)
  • Resch, N.A. (Nicolas)
  • Xing, C. (Chaoping)
Publication Date
Feb 01, 2021
Identifiers
DOI: 10.1007/s00493-020-4360-1
OAI: oai:cwi.nl:30595
Source
Repository CWI Amsterdam
Language
English
License
Unknown
External links

Abstract

For a vector space Fn over a field F, an (η, β)-dimension expander of degree d is a collection of d linear maps Γj: Fn→ Fn such that for every subspace U of Fn of dimension at most ηn, the image of U under all the maps, ∑j=1dΓj(U), has dimension at least α dim(U). Over a finite field, a random collection of d = O(1) maps Γj offers excellent “lossless” expansion whp: β≈d for η ≥ Ω(1/d). When it comes to a family of explicit constructions (for growing n), however, achieving even modest expansion factor β = 1+ ε 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 β ≥ (1 − ε)d and η≥1−εd with d = Oε(1), when | F| ≥ Ω(n).Optimal up to constant factors e

Report this publication

Statistics

Seen <100 times