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 II. -- Emergence of the Johnson Graphs

## Graph Isomorphism in Quasipolynomial Time II. -- Emergence of the Johnson GraphsAdd to your list(s) Download to your calendar using vCal - László Babai (Chicago)
- Wednesday 13 April 2016, 14:30-16:00
- CMS, MR14.
If you have a question about this talk, please contact HoD Secretary, DPMMS. Lecture II 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, MR14
- DPMMS Lists
- DPMMS info aggregator
- DPMMS lists
- Hanchen DaDaDash
- Interested Talks
- School of Physical Sciences
- Special DPMMS Colloquium
- bld31
Note that ex-directory lists are not shown. |
## Other listsThe History of Science Test de ligne de prière Type the title of a new list here## Other talksPart IIB Poster Presentations From ‘Do Not Touch’ signs to barriers: can we successfully provide access without compromising preservation principles? Carers and Careers: The Impact of Caring on Academic Careers Roland the Hero Cafe Synthetique: Synthetic Biology Industry Night Bank credit rating changes, capital structure adjustments and lending |