COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > tms41's list > On the Graph Isomorphism Problem: Breaking the Bounded Eigenvalue Multiplicity Barrier

## On the Graph Isomorphism Problem: Breaking the Bounded Eigenvalue Multiplicity BarrierAdd 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. |
## Other listsMaking more from your research – Impact & value Meeting the Challenge of Healthy Ageing in the 21st Century Neonatal Neuroscience Seminars Philomathia Forum 2017 Cancer Research UK Cambridge Institute (CRUK CI) Seminars in Cancer## Other talksProtein Folding, Evolution and Interactions Symposium Summer Cactus & Succulent Show Pruning and grafting syntactic trees for cross-lingual transfer tasks Reforming the Chinese Electricity System: A Review of the Market Reform Pilot in Guangdong Feeding your genes: The impact of nitrogen availability on gene and genome sequence evolution Intrinsically Motivating Teachers;STIR's use of Data Driven Insight to Iterate, Pivot and (where necessary) Fail Fast 'Honouring Giulio Regeni: a plea for research in risky environments' Animal Migration A new proposal for the mechanism of protein translocation Computing knot Floer homology The role of the oculomotor system in visual attention and visual short-term memory Intelligent Self-Driving Vehicles |