[Colloquium] Revised location for today's Theory Seminar

[Sandra Wallace]

*Please note that this seminar will now take place in Kent 120 at 3:00 pm and refreshments will be served after the talk in Ry. 255 at 4:00 pm*

Departments of Computer Science & Mathematics
Combinatorics & Theoretical Computer Science Seminar

László Babai
University of Chicago

Tuesday, November 10, 2015
3:00 pm
Kent 120

Abstract:

In a series of two talks we outline an algorithm that solves the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (SI) and Coset Intersection (CI) in quasipolynomial (exp(polylog n)) time.

The best previous bound for GI was  exp(sqrt{n log n}), where n is the number of vertices (Luks, 1983).  For SI and CI the best previous bound was similar,  exp(sqrt{n}(log n)^c), where n is the size of the permutation domain (the speaker, 1983).

In this first talk we give an overview of the algorithm and present the core group-theoretic divide-and-conquer routine, the “Local Certificates algorithm.” 

Familiarity with undergraduate-level group theory will be assumed.

Refreshments will be served after the talk in Ry. 255 @ 4:00 pm

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