Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-122 | 22nd November 2007 00:00

Towards Dimension Expanders Over Finite Fields


Authors: Zeev Dvir, Amir Shpilka
Publication: 7th December 2007 11:34
Downloads: 3088


In this paper we study the problem of explicitly constructing a
{\em dimension expander} raised by \cite{BISW}: Let $\mathbb{F}^n$
be the $n$ dimensional linear space over the field $\mathbb{F}$.
Find a small (ideally constant) set of linear transformations from
$\F^n$ to itself $\{A_i\}_{i \in I}$ such that for every linear
subspace $V \subset \F^n$ of dimension $\dim(V) < n/2$ we have
$$\dim\left(\sum_{i \in I} A_i(V) \right) \geq (1+\alpha) \cdot
\dim(V),$$ where $\alpha >0$ is some constant. In other words, the
dimension of the subspace spanned by $\{ A_i(V) \}_{i\in I}$
should be at least $(1+\alpha) \cdot \dim(V)$. For fields of
characteristic zero Lubotzky and Zelmanov \cite{LubotzkyZelmanov}
completely solved the problem by exhibiting a set of matrices, of
size independent of $n$, having the dimension expansion property.
In this paper we consider the finite field version of the problem
and obtain the following results:
1) We give a constant number of matrices that expand the dimension of every
subspace of dimension $d < n/2$ by a factor of $(1 + 1/\log n)$.

2) We give a set of $O(\log n)$ matrices with expanding factor
of $(1+\alpha)$, for some constant $\alpha>0$.

Our constructions are algebraic in nature and rely on expanding
Cayley graphs for the group $\mathbb{Z}/\mathbb{Z}n$ and
small-diameter Cayley graphs for the group $\mathrm{SL}_2(p)$.

ISSN 1433-8092 | Imprint