On the Graph Isomorphism Problem: Breaking the Bounded Eigenvalue Multiplicity Barrier

Add to your list(s) Download to your calendar using vCal

• Robert Elsaesser (University of Salzburg)
• Monday 03 February 2014, 11:00-12:00
• Computer Laboratory, Room FW11.

If you have a question about this talk, please contact Dr Thomas Sauerwald.

Graph Isomorphism is one of the most prominent problems in computer 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 bounded multiplicity (except at most one eigenvalue), this problem is in P. Although this result has been reproved several times – with different techniques – the boundary has not been extended beyond constant eigenvalue multiplicity so far (except w.r.t.~one single eigenvalue as mentioned above, see second algorithm of Babai, Grigoryev, and Mount, STOC 1982 ).

We show that if for two graphs the sum of squares of the multiplicities corresponding to the eigenvalues with unbounded multiplicity is O(\log n / \log \log n), where n is the number of vertices, then isomorphism testing can be solved in polynomial time. In order to overcome the problems occurring in previous algorithms w.r.t. these graphs, we apply an approximative approach to obtain orthogonal transformations, which correspond to permutations of the automorphism group of such a graph and operate on the spaces of the eigenvalues with unbounded multiplicity. This approach is then coupled with an adapted version of the first algorithm of Babai, Grigoryev, and Mount. Our result and technique provide further insight into the connection between graph spectra and the Graph Isomorphism problem.

This talk is part of the tms41's list series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, Room FW11
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.