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:tms41's list
SUMMARY:On the Graph Isomorphism Problem: Breaking the Bou
nded Eigenvalue Multiplicity Barrier - Robert Elsa
esser (University of Salzburg)
DTSTART;TZID=Europe/London:20140203T110000
DTEND;TZID=Europe/London:20140203T120000
UID:TALK50586AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/50586
DESCRIPTION:Graph Isomorphism is one of the most prominent pro
blems in computer science\, for which it is not kn
own to be NP-complete or polynomial time solvable.
More than three decades ago\, Babai\, Grigoryev\,
and Mount (STOC 1982) showed that for graphs\, wh
ich only have eigenvalues of bounded multiplicity
(except at most one eigenvalue)\, this problem is
in P. Although this result has been reproved sever
al times - with different techniques - the\nbounda
ry has not been extended beyond constant eigenvalu
e multiplicity so far (except w.r.t.~one single ei
genvalue as mentioned above\, see second algorithm
of Babai\, Grigoryev\, and Mount\, STOC 1982).\n\
nWe show that if for two graphs the sum of squares
of the multiplicities corresponding to the eigenv
alues with unbounded multiplicity is O(\\log n / \
\log \\log n)\, where n is the number of vertices\
, then isomorphism testing can be solved in polyno
mial time. In order to overcome the problems occur
ring in previous algorithms w.r.t. these graphs\,
we apply an approximative approach to obtain ortho
gonal transformations\, which correspond to permut
ations of the automorphism group of such a graph a
nd operate on the spaces of the eigenvalues with u
nbounded multiplicity. This approach is then coupl
ed with an adapted version of the first algorithm
of Babai\, Grigoryev\, and Mount. Our result and t
echnique provide further insight into the connecti
on between graph spectra and the Graph Isomorphism
problem.
LOCATION:Computer Laboratory\, Room FW11
CONTACT:Dr Thomas Sauerwald
END:VEVENT
END:VCALENDAR