COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Special DPMMS Colloquium > Graph Isomorphism in Quasipolynomial Time I. -- Local Certificates

## Graph Isomorphism in Quasipolynomial Time I. -- Local CertificatesAdd to your list(s) Download to your calendar using vCal - Laszlo Babai (Chicago)
- Tuesday 12 April 2016, 14:30-16:00
- CMS, MR2.
If you have a question about this talk, please contact HoD Secretary, DPMMS. This talk has been canceled/deleted Towards the end of 2015, Professor Laszlo Babai of the University of Chicago announced a result which was immediately hailed as the best result in complexity theory for several decades. He will give two 90-minute talks on this result of his in CMS , (12th and 13th April) in which he hopes to give a fairly detailed outline of his proof. These talks are aimed at a general audience, and are distinct from his talk on Thursday in the “Quantum Algorithms” workshop. One of the fundamental computational problems in the complexity class NP on Karp’s 1973 list, the Graph Isomorphism problem (GI) asks to decide whether or not two given graphs are isomorphic. While program packages exist that solve this problem remarkably efficiently in practice (McKay, Piperno, and others), for complexity theorists the problem has been notorious for its unresolved asymptotic worst-case complexity: strong theoretical evidence suggests that the problem should not be NP-complete, yet the worst-case complexity has stood at $\exp(O(\sqrt{v\log v}))$ (Luks, 1983) for decades, where $v$ is the number of vertices. By addressing the bottleneck situation for Luks’s method, we have recently reduced this ``moderately exponential’’ upper bound to quasipolynomial, i.e., $\exp((\log v)^c)$. We actually solve the more general We attack the bottleneck situation for Luks’s method through local/global interaction. Key role is played by a group theoretic lemma that enables the construction of global automorphisms out of local information. The lemma is used to create ``local certificates’’ of full symmetry or its absence. Subsequently the local certificates are aggregated to a canonically embedded structure which is then exploited to produce a significant reduction of the problem size at moderate multiplicative cost, leading to quasipolynomial recurrence. This reduction is accomplished via combinatorial partitioning techniques. The first talk will focus on the core group theoretic method; in the second talk we shall discuss the combinatorial partitioning techniques. Elements of undergraduate-level group theory will be assumed. The paper is available at arXiv:1512.03547. 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. This talk is part of the Special DPMMS Colloquium series. ## This talk is included in these lists:This talk is not included in any other list Note that ex-directory lists are not shown. |
## Other listsScience meets Faith Visual rhetoric and modern South Asian history Economic orthodoxy and barriers to the low-carbon economy EPRG Energy and Environment Seminar Series Lent 2009 Type the title of a new list here jer64's list## Other talksPOSTPONED - Acoustics in the 'real world' - POSTPONED Translational Science: using biomarkers to guide clinical development in oncology Action Stations! Analytical Ultracentrifugation (AUC) Roland the Hero |