[Colloquium] Talk by Paolo Codenotti, University of Chicago on January 26, 2009

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Monday, January 26, 2009
Time: 3:45 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:	Paolo Codenotti

From:		University of Chicago

Website: 	http://www.cs.uchicago.edu/people/paoloc

Title:    Isomorphism of Hypergraphs of Low Rank in Moderately  
Exponential Time

Abstract:    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.



Refreshments will be served prior to the talk in RY 255 at 3:00.