Tutte seminar - David Jao

Constructing expander graphs from the Generalized Riemann Hypothesis

Abstract:

We present a construction of expander graphs obtained from Cayley graphs of narrow ray class groups, whose eigenvalue bounds follow from the Generalized Riemann Hypothesis. Our result implies that the Cayley graph of $(\mathbf{Z}/q\mathbf{Z})^*$ with respect to small prime generators is an expander. As another application, we explain the relationship between the expansion properties of these graphs and the security of the elliptic curve discrete logarithm problem.

Joint work with Stephen D. Miller and Ramarathnam Venkatesan.