ELC Seminar (Dr. David Rosenbaum)
| Time & Date | March 22nd(Tue) 13:30-14:30 | |
|---|---|---|
| Place | CELC (Center for ELC), Seminar room (Rm. 404) | |
| Speaker | Dr. David Rosenbaum (The University of Tokyo) | |
| Title | Algorithms for hard instances of group isomorphism | |
| Abstract | ||
|---|---|---|
| The group isomorphism problem asks us to determine if two groups defined by their multiplication tables are isomorphic. In addition to being of interest as a fundamental problem in computational group theory, it is a special case of the graph isomorphism problem and is a significant obstacle to improving Babai’s recent quasipolynomial-time algorithm for graph isomorphism. For several decades, the best worst-case algorithm known for difficult cases of group isomorphism was the generator-enumeration algorithm which runs in n^(log n + O(1)) time. In this talk, we consider several difficult cases of the group isomorphism problem and show improvements over the generator-enumeration algorithm.
(host: F. Le Gall and O. Watanabe, watanabe@is.titech.ac.jp) |
||