Towards dimension expanders over finite fields

Zeev Dvir, Amir Shpilka

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

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).

Original languageEnglish (US)
Title of host publicationProceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008
Pages304-310
Number of pages7
DOIs
StatePublished - Sep 19 2008
Externally publishedYes
Event23rd Annual IEEE Conference on Computational Complexity, CCC 2008 - College Park, MD, United States
Duration: Jun 23 2008Jun 26 2008

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Other

Other23rd Annual IEEE Conference on Computational Complexity, CCC 2008
CountryUnited States
CityCollege Park, MD
Period6/23/086/26/08

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Towards dimension expanders over finite fields'. Together they form a unique fingerprint.

  • Cite this

    Dvir, Z., & Shpilka, A. (2008). Towards dimension expanders over finite fields. In Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008 (pp. 304-310). [4558832] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2008.19