[Colloquium] REMINDER: Talk by Paolo Codenotti Today

[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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20090126/20f21587/attachment.htm