Towards dimension expanders over finite fields |
| |
| Authors: | Zeev Dvir Amir Shpilka |
| |
| Affiliation: | 1. Dept. of Mathematics Dept. of Computer Science, Princeton University, Princeton, NJ, USA
2. Faculty of Computer Science, Technion - Israel Institute of Technology, Haifa, Israel
|
| |
| Abstract: | In this paper we study the problem of explicitly constructing a dimension expander raised by [3]: Let mathbbFn mathbb{F}^n be the n dimensional linear space over the field mathbbFmathbb{F}. Find a small (ideally constant) set of linear transformations from mathbbFn mathbb{F}^n to itself {A i } i∈I such that for every linear subspace V ⊂ mathbbFn mathbb{F}^n of dimension dim(V)<n/2 we have | dim( ?i ? I Ai (V) ) geqslant (1 + a) ·dim(V),dim left( {sumlimits_{i in I} {A_i (V)} } right) geqslant (1 + alpha ) cdot dim (V), |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
|
