[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

*REMINDER*

Theory Speaker 
Tuesday, October 15, 2013
3:00 p.m.
Ryerson 251
 
John Wilmes
University of Chicago-Math
www.math.uchicago.edu
 
Title:  “On testing isomorphism of strongly regular graphs”
 
Abstract: Strongly regular (s.r.) graphs have long been identified as a hard
although probably not complete class for the Graph Isomorphism (GI)problem.  We show that isomorphism of s.r. graphs with n vertices
can be tested in time exp(n^{1/5}) (we ignore logarithmic factorsin the exponent), improving the previous exp(n^{1/3}) (Spielman, STOC 1996).  One of the novelties is that we make Luks's group theoretic divide-and-conquer methods bear upon the problem via a result of Babai-Luks (1983).  The results partly depend on a new "clique geometry" we discover in certain range of the parameters.
 
Another ingredient of the main result is an n^{log n} isomorphism test for Steiner desings; the best previous bound for that case was exp(sqrt{n}) (Babai-Pyber 1994, Spielman 1996).
 
Joint work with Laszlo Babai and partly simultaneous and partly joint work with Xi Chen, Xiaorui Sun, and Shang-Hua Teng. Presented at STOC'13 (2+3 authors) and FOCS'13 (5 authors).  The FOCS paper has been invited to SICOMP's FOCS'13 Special Issue.
 
Host: Prof. Laszlo Babai
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 
 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20131015/1fd7cb82/attachment.htm