Towards dimension expanders over finite fields |
| |
| Authors: | Zeev Dvir Amir Shpilka |
| |
| Institution: | 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
\mathbbF\mathbb{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( {\sum\limits_{i \in I} {A_i (V)} } \right) \geqslant (1 + \alpha ) \cdot \dim (V), |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
|
