Colloquium-Detecting properties from descriptions of groups
Fri, 23 March, 2018
5:00pm
Title: Detecting properties from descriptions of groups
Speaker: Jennifer Chubb, University of San Francisco and GWU
http://www.cs.usfca.edu/~
Date and Time: Friday, March 23, 1:00-2:00pm
Place: Rome 204
Abstract : The complexity of the word, conjugacy, and isomorphism problems of finitely presented groups have long been of interest in combinatorial group theory, logic, and algebra in general. Motivating questions are whether (and ideally, how) the presentation of a group in terms of generators and relators can shed any light on the existence of algorithms that solve these problems, or whether the groups exhibit other properties of interest. These questions are usually formulated as what we'll call detection problems, questions of the form "Does presentation P yield a group which exhibits property P?"
We consider detection problems in two classes of descriptions of groups. The first is the class of recursive presentations of groups, in which we are given an algorithm that identifies the generators and relators in the presentation. The second is from the point of view of computable structure theory, from which we consider another type of algorithmic description of a group, its computable atomic diagram.
From either perspective we are asking whether, given a simple, finite description of a group in the form of an algorithm, it is possible to effectively determine whether or not the group has some specified property. When there is such an effective procedure, we say the property s recursively recognizable wit
We were originally motivated by a desire to determine from a recursive presentation or atomic diagram whether or not a group is orderable. While we will see results in that vein, we will begin by considering a much broader class of properties, and see precise characterizations of the algorithmic complexity of the detection problems for many of them.
This work is joint with Iva Bilanovic and Sam Roven.
Bio: Jennifer Chubb received her PhD from George Washington University in 2009, where she studied mathematical logic and computability theory. Her main interests are in computable structure theory, and the algorithmically accessible content of mathematics in general. In a previous life, she studied physics, applied math, and non-linear dynamics at George Mason University. Jennifer is an Associate Professor at the University of San Francisco's Department of Mathematics in California, and visiting scholar at George Washington University.