Computer Science Program and Dean of the College Present
Computational Complexity of Isomorphism Testing
Thursday, December 8, 2022
RKC 111
5:00 pm – 6:00 pm EST/GMT-5
5:00 pm – 6:00 pm EST/GMT-5
Michael Levet, Colorado State University
The Graph Isomorphism problem takes as input two graphs and asks if they are the same up to a relabeling of the vertices. This natural problem is not known to admit an efficient (polynomial-time) algorithm, and it is even conjectured that no such algorithm exists. In this talk, I will introduce classical color refinement techniques, including their role in state of the art theoretical and practical advances for Graph Isomorphism. I will then discuss some of my recent results on a crucial algebraic subproblem called Group Isomorphism, which were obtained by leveraging these classical color refinement techniques for isomorphism testing in graphs. I will conclude by highlighting several accessible open questions that could serve as the basis for student research projects.For more information, call 845-758-6822, or e-mail [email protected].
Time: 5:00 pm – 6:00 pm EST/GMT-5
Location: RKC 111