Dimension expanders

Abstract: We show that there exists

and

such that for every field

F

of characteristic zero and for every

, there exists explicitly given linear transformations

T_{1}, ..., T_{k} : F^{n} o F^{n}

satisfying the following: For every subspace

W

of

F^{n}

of dimension less or equal

f r a c n 2

,

d i m (W + s u m l_{i = 1}^{k} T_{i} W) g e (1 + e) d i m W

. This answers a question of Avi Wigderson [W]. The case of fields of positive characteristic (and in particular finite fields) is left open.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: Dimension expanders