### Abstract

In this paper we study the problem of explicitly constructing a dimension expander raised by [3]: Let double-struck F sign^{n} 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 {A_{i}}_{iεI} such that for every linear subspace V ⊂ double-struck F sign^{n} of dimension dim(V) < n/2 we have dim (Σ_{iεI}A_{i}(V)) > (l+α) ·dim(V), where α > 0 is some constant. In other words, the dimension of the subspace spanned by {A_{i}(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 SL_{2}(p).

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008 |

Pages | 304-310 |

Number of pages | 7 |

DOIs | |

State | Published - Sep 19 2008 |

Externally published | Yes |

Event | 23rd Annual IEEE Conference on Computational Complexity, CCC 2008 - College Park, MD, United States Duration: Jun 23 2008 → Jun 26 2008 |

### Publication series

Name | Proceedings of the Annual IEEE Conference on Computational Complexity |
---|---|

ISSN (Print) | 1093-0159 |

### Other

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

Country | United States |

City | College Park, MD |

Period | 6/23/08 → 6/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

*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