Joint Algorithms, Combinatorics & Optimization/Theory Seminar

Friday, January 22, 2016 - 1:30pm to 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

For More Information, Contact:

anupamg@cs.cmu.edu

Keywords:

Seminar Series