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 - László 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. Lecture I Two 90-minute talks will be given, about testing graph isomorphism in quasipolynomial time. These talks are aimed at a general audience, and are distinct from the 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:- All CMS events
- All Talks (aka the CURE list)
- CMS Events
- CMS, MR2
- DPMMS Lists
- DPMMS info aggregator
- DPMMS lists
- Interested Talks
- School of Physical Sciences
- Special DPMMS Colloquium
- bld31
Note that ex-directory lists are not shown. |
## Other listsSchool of Technology Cosmology, Astrophysics and General Relativity mySociety Meetups## Other talksDive into the Lives of Flies and Ants White dwarfs as tracers of cosmic, galactic, stellar & planetary evolution The role of Birkeland currents in the Dungey cycle First order rigidity of higher rank arithmetic lattices (note the nonstandard day) Cancer and Metbolism 2018 Analytical Ultracentrifugation (AUC) |