What is an expander?

Document Type : Translation Paper

Author

University of Isfahan

Abstract

This paper is a translation of the the following paper into Persian:
[Peter Sarnak, What is an Expander?, Notices of The American Mathematical Society, 51 no. 7 (2004) 762–763.]

construction of finitely generated groups which cannot be embedded uniformly in a Hilbert space (Gromov) and related counterexamples to the Baum-Connes conjectures for group actions. However, it is in applications in theoretical computer science where expanders have had their major impact. Among their applications are the design of explicit superefficient communication networks, constructions of errorcorrecting codes with very efficient encoding and decoding algorithms, derandomization of random algorithms, and analysis of algorithms in computational group theory (see for example [O. Reingold, S. Vadhan, and A. Wigderson, Ann. of Math., 155 (2002) 157–187.])

References

[1] A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica, 8 (1988) 261–277.
[2] G. Margulis, Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of ex-panders and concentrators, Problems Inform, Transmission, 24 (1988) 39–46.
[3] O. Reingold, S. Vadhan and A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders, Ann. of Math. (2), 155 (2002) 157–187.
Mathematics and Society
Volume 1, Issue 4 - Serial Number 4
December 2016
Pages 7-10

Files

Share

How to cite

Statistics