[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

*REMINDER*

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

László Babai
University of Chicago

Tuesday, November 10, 2015
3:00 pm
Ryerson 251

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 prior to the talk in Ry. 255 @ 2:30pm

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