BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:Expander graphs based on GRH and some cryptographi
c applications - Ramarathnam Venkatesan (Microsoft
Research)
DTSTART;TZID=Europe/London:20090116T120000
DTEND;TZID=Europe/London:20090116T130000
UID:TALK16348AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/16348
DESCRIPTION:CANCELLED due to illness\n\nWe present a construct
ion of expander graphs obtained from Cayley graphs
of narrow ray class groups\, whose eigenvalue bou
nds follow from the Generalized Riemann Hypothesis
. Our result implies that the Cayley graph of (Z/q
Z)* with respect to small prime generators is an e
xpander.\n\nAs another application\, we show that
the graph of small prime degree isogenies between
ordinary elliptic curves achieves non-negligible e
igenvalue separation\, and explain the relationshi
p between the expansion properties of these graphs
and the security of the elliptic curve discrete l
ogarithm problem. Finally we show that the least
significant bit of $x(abP)$ is pseudo-random giv
en $(aP\,bP\,P)$\, using these results and a refin
ement of Lenstra's result on distribution of order
s of elliptic curves.\n\nBased on works with Steph
en D Miller (Rutgers) David Jao (Waterloo) and Dim
itar Jetchev (UC Berkeley).\n
LOCATION:MR11
CONTACT:Andrew Thomason
END:VEVENT
END:VCALENDAR