Friday, November 28, 2008
3:30 pm, MC 5158

Tutte Seminar Series
Combinatorics & Optimization
Fall 2008


David Jao
University of Waterloo

Constructing expander graphs from the Generalized Riemann Hypothesis

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.