Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-001 | 31st December 2000 00:00

Essentially every unimodular matrix defines an expander

RSS-Feed




TR01-001
Authors: Jin-Yi Cai
Publication: 3rd January 2001 14:49
Downloads: 3956
Keywords: 


Abstract:

We generalize the construction of Gabber and Galil
to essentially every unimodular matrix in $SL_2(\Z)$. It is shown that
every parabolic
or hyperbolic fractional linear transformation explicitly
defines an expander of bounded degree
and constant expansion. Thus all but a vanishingly small fraction
of unimodular matrices define expanders.



ISSN 1433-8092 | Imprint