BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:On the Graph Isomorphism Problem: Breaking the Bounded Eigenvalue 
 Multiplicity Barrier - Robert Elsaesser (University of Salzburg)
DTSTART:20140203T110000Z
DTEND:20140203T120000Z
UID:TALK50586@talks.cam.ac.uk
CONTACT:Dr Thomas Sauerwald
DESCRIPTION:Graph Isomorphism is one of the most prominent problems in com
 puter science\, for which it is not known to be NP-complete or polynomial 
 time solvable. More than three decades ago\, Babai\, Grigoryev\, and Mount
  (STOC 1982) showed that for graphs\, which only have eigenvalues of bound
 ed multiplicity (except at most one eigenvalue)\, this problem is in P. Al
 though this result has been reproved several times - with different techni
 ques - the\nboundary has not been extended beyond constant eigenvalue mult
 iplicity so far (except w.r.t.~one single eigenvalue 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 corre
 sponding to the eigenvalues with unbounded multiplicity is O(\\log n / \\l
 og \\log n)\, where n is the number of vertices\, then isomorphism testing
  can be solved in polynomial time. In order to overcome the problems occur
 ring in previous algorithms w.r.t. these graphs\, we apply an approximativ
 e approach to obtain orthogonal transformations\, which correspond to perm
 utations of the automorphism group of such a graph and operate on the spac
 es of the eigenvalues with unbounded multiplicity. This approach is then c
 oupled with an adapted version of the first algorithm of Babai\, Grigoryev
 \, and Mount. Our result and technique provide further insight into the co
 nnection between graph spectra and the Graph Isomorphism problem.
LOCATION:Computer Laboratory\, Room FW11
END:VEVENT
END:VCALENDAR