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).>

We present polynomial-time algorithms for computation in quotient groups G/K of a permutation group G.In effect, these solve, for quotient groups, the problems that are known to be in polynomial-time for permutation groups.Since it is not computationally feasible to represent G/K itself as a permutation group, the methodology for the quotient-group versions of such problems frequently differ markedly from the procedures that have been observed for the K = 1 subcases.Whereas the algorithms for permutation groups may have rested on elementary notions, procedures underlying the extension to quotient groups often utilize deep knowledge of the structure of the group.In some instances, we present algorithms for problems that were not previously known to be in polynomial time, even for permutation groups themselves (K = 1).These problems apparently required access to quotients.

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.

Ifmis odd and\sigma /in Aut GF(2^{m})is such thatx \rightarrow x^{\sigma^{2}-1}is1-1, there is a[2^{m+1}-1,2^{m+l}-2m-2]nonlinear binary codeP(\sigma)having minimum distance 5. All the codesP(\sigma)have the same distance and weight enumerators as the usual Preparata codes (which rise asP(\sigma)whenx^{\sigma}=x^{2}). It is shown thatP(\sigma)andP(\tau)are equivalent if and only if\tau=\sigma^{\pm 1}, andAut P(\sigma)is determined.

Letn \equiv 0 \pmod{8}. Then there are two self-dual binary codes of lengthnhaving only the zero and all-one vectors in common, having all weights divisible by four, and having minimum distances asymptotically the same as that given by the Varshamov-Gilbert bound.