Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-017 | 26th January 2018 16:17

Lossless dimension expanders via linearized polynomials and subspace designs



For a vector space $\mathbb{F}^n$ over a field $\mathbb{F}$, an $(\eta,\beta)$-dimension expander of degree $d$ is a collection of $d$ linear maps $\Gamma_j : \mathbb{F}^n \to \mathbb{F}^n$ such that for every subspace $U$ of $\mathbb{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 \approx d$ for $\eta \geq \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 \geq (1-\epsilon)d$ and $\eta \geq \frac{1-\epsilon}{d}$ with $d = O_{\epsilon}(1)$, when $|\mathbb{F}| \geq \Omega(n)$.

* Optimal up to constant factors expansion over fields of arbitrarily small polynomial size; more precisely $\beta \geq \Omega(\delta d)$ and $\eta \geq \Omega(1/(\delta d))$ with $d=O_\delta(1)$, when $|\mathbb{F}| \geq 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 \geq \Omega(\sqrt{d})$ over large finite fields. Ours is the first construction to achieve lossless dimension expansion, or even expansion proportional to the degree.

ISSN 1433-8092 | Imprint