TY - GEN

T1 - Towards dimension expanders over finite fields

AU - Dvir, Zeev

AU - Shpilka, Amir

PY - 2008

Y1 - 2008

N2 - In this paper we study the problem of explicitly constructing a dimension expander raised by [3]: Let double-struck F signn be the n dimensional linear space over the field double-struck F sign. Find a small (ideally constant) set of linear transformations from double-struck F sign n to itself {Ai}iεI such that for every linear subspace V ⊂ double-struck F signn of dimension dim(V) < n/2 we have dim (ΣiεIAi(V)) > (l+α) ·dim(V), where α > 0 is some constant. In other words, the dimension of the subspace spanned by {Ai(V)} iεI should be at least (1 + α) · dim(V). For fields of characteristic zero Lubotzky and Zelmanov [8] 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 + α), for some constant α > 0. Our constructions are algebraic in nature and rely on expanding Cayley graphs for the group ℤ/ℤn and smalldiameter Cayley graphs for the group SL2(p).

AB - In this paper we study the problem of explicitly constructing a dimension expander raised by [3]: Let double-struck F signn be the n dimensional linear space over the field double-struck F sign. Find a small (ideally constant) set of linear transformations from double-struck F sign n to itself {Ai}iεI such that for every linear subspace V ⊂ double-struck F signn of dimension dim(V) < n/2 we have dim (ΣiεIAi(V)) > (l+α) ·dim(V), where α > 0 is some constant. In other words, the dimension of the subspace spanned by {Ai(V)} iεI should be at least (1 + α) · dim(V). For fields of characteristic zero Lubotzky and Zelmanov [8] 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 + α), for some constant α > 0. Our constructions are algebraic in nature and rely on expanding Cayley graphs for the group ℤ/ℤn and smalldiameter Cayley graphs for the group SL2(p).

UR - http://www.scopus.com/inward/record.url?scp=51749108893&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51749108893&partnerID=8YFLogxK

U2 - 10.1109/CCC.2008.19

DO - 10.1109/CCC.2008.19

M3 - Conference contribution

AN - SCOPUS:51749108893

SN - 9780769531694

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 304

EP - 310

BT - Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008

T2 - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008

Y2 - 23 June 2008 through 26 June 2008

ER -