**TITLE:** A nilpotent quotient algorithm for graded Lie rings

**AUTHORS:** George Havas, M. F. Newman and M. R. Vaughan-Lee

**CITATION:** Journal of Symbolic Computation **9** (1990) 655-664 (open archive)

**ABSTRACT:** A nilpotent quotient algorithm for graded Lie rings of prime characteristic is described. The algorithm has been implemented and applications have been made to the investigation of the associated Lie rings of Burnside groups. New results about Lie rings and Burnside groups are presented. These include detailed information on groups of exponent 5 and 7 and their associated Lie rings.

**TITLE:** Coset enumeration strategies

**AUTHOR:** George Havas

**CITATION:** *ISSAC'91* (Proc. 1991 International Symposium on Symbolic and Algebraic Computation), ACM Press (1991) 191-199

**ABSTRACT:** A primary reference on computer implementation of coset enumeration procedures is a 1973 paper of Cannon, Dimino, Havas and Watson. Programs and techniques described there are updated in this paper. Improved coset definition strategies, space saving techniques and advice for obtaining improved performance are included. New coset definition strategies for Felsch-type methods give substantial reductions in total cosets defined for some pathological enumerations. Significant time savings are achieved for coset enumeration procedures in general. Statistics on performance are presented, both in terms of time and in terms of maximum and total cosets defined for selected enumerations.

**TITLE:** An optimal algorithm for generating minimal perfect hash functions

**AUTHORS:** Zbigniew J. Czech, George Havas and Bohdan S. Majewski

**CITATION:** Information Processing Letters **43** (1992) 257-264

**ABSTRACT:** A new algorithm for generating order preserving minimal perfect hash functions is presented. The algorithm is probabilistic, involving generation of random graphs. It uses expected linear time and requires a linear number words to represent the hash function, and thus is optimal up to constant factors. It runs very fast in practice.

**TITLE:** Algorithms for groups

**AUTHORS:** John Cannon and George Havas

**CITATION:** *Australian Computer Journal* **24** (1992) 51-60

**ABSTRACT:** Group theory is a particularly fertile field for the design of practical algorithms. Algorithms have been developed across the various branches of the subject and they find wide application. Because of its relative maturity, computational group theory may be used to gain insight into the general structure of algebraic algorithms. This paper examines the basic ideas behind some of the more important algorithms for finitely presented groups and permutation groups, and surveys recent developments in these fields.

[Reprint: 822K]

**TITLE:** Optimal Algorithms for Minimal Perfect Hashing

**AUTHORS:** George Havas and Bohdan S. Majewski

**CITATION:** Technical Report 234, The University of Queensland (1992)

**ABSTRACT:** We review previous methods for finding minimal perfect hash functions, showing that the earlier ones have no serious practical value for large sets. Then we present optimal time solutions to the problem, which generate minimal perfect hash functions for arbitrary sets in expected linear time and use almost linear space. The hash functions are fast computable. We give examples of performance for large sets.

**TITLE:** Application of substring searching methods to group presentations

**AUTHORS:** George Havas and Mark Ollila

**CITATION:** *Australian Computer Science Communications* **15** (1993) 587-593

**ABSTRACT:** An important way for describing groups is by finite presentations. Large presentations arise in practice which are poorly suited for either human or computer use. Presentation simplification processes which take bad presentations and produce good presentations have been developed. Substantial use is made of substring searching and appropriate techniques for this context are described. Effective use is made of signatures and change flags. Change flags are shown to be the most beneficial of the methods tested here, with very significant performance improvement. Experimental performance figures are given.

**TITLE:** Recognizing badly presented Z-modules

**AUTHORS:** George Havas, Derek F. Holt and Sarah Rees

**CITATION:** Linear Algebra and its Applications **192** (1993) 137-164 (open archive)

**ABSTRACT:** Finitely generated Z-modules have canonical decompositions. When such modules are given in a finitely presented form there is a classical algorithm for computing a canonical decomposition. This is the algorithm for computing the Smith normal form of an integer matrix. We discuss algorithms for Smith normal form computation, and present practical algorithms which give excellent performance for modules arising from badly presented abelian groups. We investigate such issues as congruential techniques, sparsity considerations, pivoting strategies for Gauss-Jordan elimination, lattice basis reduction and computational complexity. Our results, which are primarily empirical, show dramatically improved performance on previous methods.

**TITLE:** Graph theoretic obstacles to perfect hashing

**AUTHORS:** George Havas and Bohdan S. Majewski

**CITATION:** *Congressus Numerantium* **98** (1993) 81-93

**ABSTRACT:** A number of algorithms based on quasi-random graphs for generating perfect hash functions have been published. These include Sager's mincycle algorithm, a modification by Fox et al. of it and finally probabilistic methods due to Czech, Havas and Majewski. Each of these algorithms exploits different properties of graphs, such as being bipartite or being acyclic. In this paper we formally justify the significance of these properties. Also we indicate causes of failure for some methods. In particular we show that acyclicity of a graph plays a crucial role in finding order preserving perfect hash functions. It is a sufficient, but not necessary, condition for algorithms to actually find a perfect hash function. We provide some examples for which various published methods methods fail, taking exponential time to do so. Finally, based on our considerations of graph properties, we propose yet another method for generating perfect hash functions.

**TITLE:** Graphs, hypergraphs and hashing

**AUTHORS:** George Havas, Bohdan S. Majewski, Nicholas C. Wormald and Zbigniew J. Czech

**CITATION:** *Graph-Theoretic Concepts in Computer Science*, Lecture Notes in Computer Science **790** (1994), 153-165

**ABSTRACT:** Minimal perfect hash functions are used for memory efficient storage and fast retrieval of items from static sets. We present an infinite family of efficient and practical algorithms for generating minimal perfect hash functions which allow an arbitrary order to be specified for the keys. We show that almost all members of the family are space and time optimal, and we identify the one with minimum constants. Members of the family generate a minimal perfect hash function in two steps. First a special kind of function into an r-graph is computed probabilistically. Then this function is refined deterministically to a minimal perfect hash function. We give strong practical and theoretical evidence that the first step uses linear random time. The second step runs in linear deterministic time. The family not only has theoretical importance, but also offers the fastest known method for generating perfect hash functions.

**TITLE:** Application of computational tools for finitely presented groups

**AUTHORS:** George Havas and Edmund F. Robertson

**CITATION:** *Computational Support for Discrete Mathematics*, DIMACS Series in Discrete Mathematics and Theoretical Computer Science **15** (1994), 29-39

**ABSTRACT:** Computer based techniques for recognizing finitely presented groups are quite powerful. Tools available for this purpose are outlined. They are available both in stand-alone programs and in more comprehensive systems. A general computational approach for investigating finitely presented groups by way of quotients and subgroups is described and examples are presented. The techniques can provide detailed information about group structure. Under suitable circumstances a finitely presented group can be shown to be soluble and its complete derived series can be determined, using what is in effect a soluble quotient algorithm.

**TITLE:** Hermite normal form computation for integer matrices

**AUTHORS:** George Havas and Bohdan S. Majewski

**CITATION:** *Congressus Numerantium* **105** (1994) 87-96

**ABSTRACT:** We consider algorithms for computing the Hermite normal form of integer matrices. Various different strategies have been proposed, primarily trying to avoid the major obstacle that occurs in such computations --- explosive growth in size of intermediate entries. We analyze some methods for computing the Hermite normal form and we show the intractability of associated problems. We investigate in detail a method based on an algorithm due to Blankinship and show how improved performance is achieved.

**TITLE:** The complexity of greatest common divisor computations

**AUTHORS:** Bohdan S. Majewski and George Havas

**CITATION:** *Algorithmic Number Theory*, Lecture Notes in Computer Science **877** (1994) 184-193

**ABSTRACT:** We consider the complexity of expressing the greatest common divisor of n positive numbers as a linear combination of the numbers. We prove the NP-completeness of finding optimal sets of multipliers with respect to both the L_{0} metric and L_{infinity} norm. We present and analyze a new method for expressing the gcd of n numbers as their linear combination and give an upper bound on the size of the largest multiplier produced by this method, which is optimal.

**TITLE:** A new problem in string searching

**AUTHORS:** George Havas and Jin Xian Lian

**CITATION:** *Algorithms and Computation*, Lecture Notes in Computer Science **834** (1994) 660-668

**ABSTRACT:** We describe a substring search problem that arises in group presentation simplification processes. We suggest a two-level searching model: skip and match levels. We give two timestamp algorithms which skip searching parts of the text where there are no matches at all and prove their correctness. At the match level, we consider Harrison signature, Karp-Rabin fingerprint, Bloom filter and automata based matching algorithms and present experimental performance figures.

**TITLE:** Reconstructing a distributed depth-first-search tree after network topology changes

**AUTHORS:** S.A.M. Makki and George Havas

**CITATION:** *Proc. Sixth IASTED/ISMM Internat. Conf. Parallel and Distributed Computing and Systems*, Acta Press (1994) 335-337

**ABSTRACT:** We consider the problem of reconstructing a distributed depth-first-search (DFS) tree in an interconnected communication network in the presence of link failures or deletions and/or recoveries or additions. We describe an algorithm which efficiently reconstructs a distributed DFS tree after several links are deleted, with link additions also properly handled. Under standard assumptions, the required number of messages and time units in the worst case is bounded by k(h+|V|(1+r)), where k is the number of link failures, h is the length of the longest simple path in the network, |V| is the number of nodes in the network and 0<=r<1.

**TITLE:** Extended gcd algorithms

**AUTHORS:** George Havas, B.S. Majewski and K.R. Matthews

**CITATION:** Technical Report 302, The University of Queensland (1995)

**ABSTRACT:** Extended gcd calculation has a long history and plays an important role in computational number theory and linear algebra. Recent results have shown that finding optimal multipliers in extended gcd calculations is difficult. We study algorithms for finding good multipliers and present new algorithms with improved performance. We present a well-performing algorithm which is based on lattice basis reduction methods and may be formally analyzed. We also give a relatively fast algorithm with moderate performance.

**TITLE:** A solution to the extended gcd problem

**AUTHORS:** Bohdan S. Majewski and George Havas

**CITATION:** *ISSAC'95* (Proc. 1995 Internat. Sympos. on Symbolic and Algebraic Computation), ACM Press (1995) 248-253

**ABSTRACT:** An improved method for expressing the greatest common divisor of n numbers as an integer linear combination of the numbers is presented and analyzed, both theoretically and practically. The performance of this algorithm is compared with other methods, indicating substantial improvements in the size of the solution. The results are given in the light of the current knowledge about the complexity of extended gcd computations. Thus, finding optimal sets of multipliers has been proved to be an NP-complete problem. We present a relatively efficient approximation algorithm with excellent performance. This problem is interesting in its own right. Furthermore, it has important applications, for example in computing canonical normal forms of integer matrices.

**TITLE:** Extended gcd calculation

**AUTHORS:** George Havas and Bohdan S. Majewski

**CITATION:** *Congressus Numerantium* **111** (1995) 104-114

**ABSTRACT:** Given an integer vector **a** of n positive numbers the extended gcd problem asks for an integer vector **x** of length n such that **x**.**a**^{T} = gcd(a_{i}). For many applications it is vital that some measure of **x** is small. We have proved, however, that if we choose either the max norm or the zero metric the question of finding **x** such that these are smaller than some positive constant K is NP-complete. We conjecture that the question remains NP-complete for other norms. In the light of these results we have proposed two approximation algorithms. Their respective complexities are O(n^{2}log(max{a_{i}})) and O(n^{4}log(max{a_{i}})). Theoretical analysis of the algorithms leads to unsatisfactory bounds on the quality of the solution. Thus here we undertake a practical study of the methods, where their performance is matched against optimal solutions.

**TITLE:** A hard problem that is almost always easy

**AUTHORS:** George Havas and B.S. Majewski

**CITATION:** *Algorithms and Computation*, Lecture Notes in Computer Science **1004** (1995) 216-223

**ABSTRACT:** NP-completeness is, in a well-defined sense, a worst case notion. Thus, 3-colorability of a graph, for a randomly generated graph, can be determined in constant expected time even though the general problem is NP-complete. The reason for this is that some hard problems exhibit a structure where only a small (perhaps exponentially small) fraction of all possible instances is intractable, while the remaining large fraction has a polynomial time solution algorithm. We add a new problem to the list of NP-complete problems that are solvable in average polynomial time.