Seminar: January 26, 2009

Paolo Codenotti, University of Chicago

Isomorphism of Hypergraphs of Low Rank in Moderately Exponential Time

We give an algorithm to decide isomorphism of k-hypergraphs in time exp(O~(k2\sqrt{n})), where n is the number of vertices. (The tilde refers to a polylogarithmic factor.) The case of bounded k answers a 24-year-old question and removes an obstacle to improving the exp(O~(\sqrt{n})) worst-case bound for Graph Isomorphism testing. The best previously known bound, even for k=3, was C^n (Luks 1999; Luks puts no restriction on k). Our analysis combines combinatorial and group theoretic methods.

Joint work with Laszlo Babai.