Joint Algorithms, Combinatorics & Optimization/Theory Seminar
— 4:30pm
Location:
ASA Conference Room 6115
-
Gates & Hillman Centers
Speaker:
LASZLO BABAI
,
Professor
http://people.cs.uchicago.edu/~laci/
The algorithm indicated in the title builds on Luks's classical framework and introduces new group theoretic and combinatorial tools. The first half of the talk will give an overview of the algorithm, outline the core group theoretic routine ("Local Certificates"), and sketch the aggregation of the local certificates. The second half of the talk will outline the combinatorial partitioning< techniques ("Design Lemma" and "Split-or-Johnson") required for ;the group-theoretic recurrence. Elements of undergraduate-level group theory such as facility with the concepts involved in the Jordan--Holder Theorem and basic concepts of permutation groups (such as orbits) will be assumed. Helpful reading:E.M. Luks : Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comp. Sys. Sci., 25:42--65, 1982.
Event Website:
http://aco.math.cmu.edu/abs-15-16/jan22.html