My research interests are on the boundary of abstract algebra and theoretical computer science. Broadly speaking, I am interested in finding ways that computer science can be brought to bear on open problems from abstract algebra. In particular, I am interested in the following areas:

• Algorithms for studying infinite groups. In theoretical computer science, we classify problems according to how difficult it is to solve them on a computer: does there exist an algorithm to solve the problem which terminates in a finite amount of time? If so, how long does it take? How much memory is needed? Most of my work in this area has focused on problems that arise in the study of infinite solvable groups. In this context most of the classical questions are computationally very difficult; therefore, the development of practical algorithms has required new theoretical insights into the structure of such groups.
• Applications of formal language theory to the study of infinite groups. Several languages are associated with an infinite groups (when the group is given by what is known as a "finite presentation"). The most famous of these is the word problem , i.e. the set of those strings, or words, that represent the identity element of the group. It is natural to ask: if we are able to classify the word problem of a given group (using the hierarchy of languages from formal language theory), what does this tell us about the group?

Refereed Journal Publications

• Baumslag, G., Miller, C.F. M., Ostheimer, G., "Recognizing decompositions in finitely generated torsion-free nilpotent groups". International Journal of Algebra and Computation 26 (2016), 1529-1546.
• Elder, M., Elston, G., Ostheimer, G., "On groups that have normal forms computable in logspace", Journal of Algebra 381 (2013), 260-281. download pdf ;
• Baumlsag, G., Miller, C. F. M., Ostheimer, G., "Subgroups of free metabelian groups", Groups, Geometry and Dynamics 4 (2010), 657-679. download pdf ;
• Elder, M., Kambites, M., Ostheimer, G., "On groups and counter automata", International Journal of Algebra and Computation 18 (2008), 1345-1364. download pdf ;
• Elston, G. and Ostheimer, G., ``On groups whose word problem is solved by a counter automaton'', Theoretical Computer Science 28 (2004), 175-185. download pdf ;
• Eick, B. and Ostheimer, G., ``On the orbit-stabilizer problem for integral matrix actions of polycyclic groups'', Mathematics of Computation 72 (2003), 1511-1529. download ps
• Ostheimer, G., ``Practical algorithms for polycyclic matrix groups'', Journal of Symbolic Computation 28 (1999), 361-379. download ps
• Lo, Eddie H. and Ostheimer, G., ``A practical algorithm for finding matrix representations for polycyclic groups'', Journal of Symbolic Computation 28 (1999), 339-360. download ps
• Fredman, M. L., Johnson, D. S., McGeoch, L. A., and Ostheimer, G., ``Data structures for traveling salesmen'', Journal of Algorithms 18 (1995), 432-479.

Refereed Conference Proceedings

• Ostheimer, G., ``Algorithms for polycyclic-by-finite matrix groups'', Groups and Computation II, ACM (1997), 297-307.
• Fredman, M. L., Johnson, D. S., McGeoch, L. A., and Ostheimer, G., ``Data structures for traveling salesmen'', Proceedings 4th Annual ACM-SIAM Symposium on Discrete Algorithms (1993), 145-154.