[Colloquium] Codenotti/Dissertation Defense/Jul 8, 2011

[Margaret Jaffey]

       Department of Computer Science/The University of Chicago

                     *** Dissertation Defense ***


Candidate:  Paolo Codenotti

Date:  Friday, July 8, 2011

Time:  2:00 PM

Place:  Ryerson 277

Title: Isomorphism Testing of Combinatorial and Algebraic Structures

Abstract:
Our main results are algorithm for isomorphism testing of hypergraphs
and of groups.

We give an algorithm to decide isomorphism of hypergraphs of rank $k$
in time $\exp(\tilde{O}(k^2\sqrt{n}))$, where $n$ is the number of
vertices (joint work with L. Babai, FOCS 2008). (The rank is the
maximum size of hyperedges; the tilde refers to a polylogarithmic
factor.) The case of bounded $k$ answers a then 24-year-old question
and removes an obstacle to improving the worst-case bound for Graph
Isomorphism testing. The best previously known bound, even for $k=3$,
was $C^n$ (Luks 1999). Our analysis combines combinatorial and group
theoretic methods.

We consider the problem of testing isomorphism of groups of order $n$
given by Cayley tables. The easy $n^{\log n}$ bound on the time
complexity for the general case has not been improved over the past
four decades. We demonstrate that the presence of abelian normal
subgroups is the only obstacle to efficient algorithms: our main
result is that ``semisimple groups,'' defined as groups without
abelian normal subgroups, admit polynomial-time isomorphism testing
(joint work with L. Babai, J. A. Grochow, Y. Qiao, SODA 2011, and L.
Babai, Y. Qiao in preparation). There are three main ingredients. (a)
A group theoretic study of the structure of semisimple groups based on
the Babai-Beals filtration of groups (L. Babai and R. Beals, Bath
1999). (b) An algorithm to test permutational isomorphism of
permutation groups in time linear in the order and exponential in the
degree. The algorithm for this problem requires an in depth analysis
of structure trees of transitive permutation groups. (c) The
introduction of and an algorithm for the ``twisted code equivalence
problem,'' a generalization of the code equivalence problem. The
problems (b) and (c) are of interest in their own right.

Paolo's advisor is Prof. Laszlo Babai

Login to the Computer Science Department website for details,
including a draft copy of the dissertation:

 https://www.cs.uchicago.edu/phd/phd_announcements#paoloc

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey            margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)               (773) 702-6011
The University of Chicago      http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=