Michael D. Atkinson

Michael D. Atkinson is a mathematician and computer scientist known for his work in the theory of permutation patterns and for contributions to algorithm design, data structures, and algebra. He is an emeritus professor at the University of Otago.

Michael D. Atkinson
Alma mater	University of Oxford
Known for	Permutation patterns, Algorithm design
Scientific career
Fields	Mathematics, Theoretical computer science
Institutions	University of Otago, University of St Andrews, Carleton University, University College, Cardiff
Thesis	Varieties of Exponent 6 and Related Topics  (1970)
Doctoral advisor	Peter M. Neumann
Doctoral students	Stephanie van Willigenburg

Education and career

Atkinson earned his B.A. (1967) and D.Phil. (1970) in mathematics from the University of Oxford, where he was a member of The Queen's College and a student of Peter M. Neumann.^[1] His doctoral work focused on varieties of groups, within the area of group theory.

He taught at University College, Cardiff from 1970 to 1982, then joined the Carleton University School of Computer Science in Canada, where he became a full professor in 1983. In 1992, Atkinson moved to the University of St Andrews as Professor of Algorithms and head of the School of Mathematical and Computational Sciences (1994–1997). He joined the University of Otago in 2000 and retired in 2012.^[2]

Research

Atkinson's early research spanned algebra, permutation groups, bilinear complexity, and algorithmic linear algebra. His 1975 paper on block-finding algorithms for permutation groups^[3] gave the first polynomial-time algorithm for the problem^[4]. He later made contributions to data structures and computational geometry, notably on min-max heaps,^[5] geometric congruence testing,^[6] the cyclic Towers of Hanoi,^[7] and frequency assignment problems in communication networks.^[8]

In the late 1990s, Atkinson shifted his research to permutation patterns^[9]. His 1999 paper Restricted permutations^[10] has been described as "foundational" in the field.^[11] In 2003, he co-founded the Permutation Patterns conference with Michael H. Albert, which has played a central role in the development of the field.^[12] Their 2005 joint paper Simple permutations and pattern restricted permutations^[13] introduced structural decomposition techniques, now known as the substitution decomposition. This work, described as "formative",^[14] refined the analysis begun in his earlier work with Tim Stitt on the wreath product.^[15] Together with Albert and Martin Klazar, Atkinson also enumerated the simple permutations that arise in this decomposition.^[16] In later work, he and co-authors introduced the notion of geometric grid classes,^[17] another tool in the study of the structure of permutation classes.