Graph Isomorphism in Quasipolynomial Time I. -- Local Certificates

Add 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 string isomorphism problem (SI) (``can a given string be transformed into another given string under the action of a given permutation group ?’‘), defined in Luks’s seminal 1980/82 paper (see below) that introduced powerful group theoretic divide-and-conquer methods in the design of SI and GI algorithms.

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.