William M. Kantor

STOC Conference 1990 Conference Paper

Computing in Quotient Groups

• William M. Kantor
• Eugene M. Luks

FOCS Conference 1990 Conference Paper

On the Diameter of Finite Groups

• László Babai
• Gábor Hetyei
• William M. Kantor
• Alexander Lubotzky
• Ákos Seress

The diameter of a group G with respect to a set S of generators is the maximum over g in G of the length of the shortest word in S union S/sup -1/ representing g. This concept arises in the contexts of efficient communication networks and Rubik's-cube-type puzzles. 'Best' generators are pertinent to networks, whereas 'worst' and 'average' generators seem more adequate models for puzzles. A substantial body of recent work on these subjects by the authors is surveyed. Regarding the 'best' case, it is shown that, although the structure of the group is essentially irrelevant if mod S mod is allowed to exceed (log mod G mod )/sup 1+c/(c>0), it plays a strong role when mod S mod =O(1). >

FOCS Conference 1983 Conference Paper

Computational Complexity and the Classification of Finite Simple Groups

• László Babai
• William M. Kantor
• Eugene M. Luks

We address the graph isomorphism problem and related fundamental complexity problems of computational group theory. The main results are these: A1. A polynomial time algorithm to test simplicity and find composition factors of a given permutation group (COMP). A2. A polynomial time algorithm to find elements of given prime order p in a permutation group of order divisible by p. A3. A polynomial time reduction of the problem of finding Sylow subgroups of permutation groups (SYLFIND) to finding the intersection of two cosets of permutation groups (INT). As a consequence, one can find Sylow subgroups of solvable groups and of groups with bounded nonabelian composition factors in polynomial time. A4. A polynomial time algorithm to solve SYLFIND for finite simple groups. A5. An ncd/log d algorithm for isomorphism (ISO) of graphs of valency less than d and a consequent improved moderately exponential general graph isomorphism test in exp(c√n log n) steps. A6. A moderately exponential, n, c√n algorithm for INT. Combined with A3, we obtain an nc√n algorithm for SYLFIND as well. All these problems have strong links to each other. ISO easily reduces to INT. A subcase of SYLFIND was solved in polynomial time and applied to bounded valence ISO in [Lul]. Now, SYLFIND is reduced to INT. Interesting special cases of SYLFIND belong to NP ∩ coNP and are not known to have subexponential solutions. All the results stated depend on the classification of finite simple groups. We note that no previous ISO test had no(d) worst case behavior for graphs of valency less than d. It appears that unless there is another radical breakthrough in ISO, independent of the previous one, the simple groups classification is an indispensable tool for further developments.