Announcement
The goal of the meeting is to assemble a small group of researchers familiar with different aspects of model theory, recursive function theory, complexity theory and combinatorial group theory to assess the extent to which forcing, priority arguments and related techniques may be applied to produce sophisticated constructions of groups with various interesting properties. The meeting will be a success if by the end a number of promising avenues for further exploration at subsequent conferences and workshops have been identified.
Combinatorial group theory has a long history of computation despite the seemingly paradoxical fact that almost all problems having to do with finitely presented groups are recursively unsolvable. On the one hand there are various classes of groups, such as word hyperbolic and automatic groups, for which many decision problems are solvable, and on the other hand there are constructions of groups with bizarre properties, e.g., Tarski monsters. It is our hope that techniques from recursive function theory and model theory which so far have not been much employed in combinatorial group theory will help to delineate the boundary between well behaved and wild groups by affording methods for constructing groups with desired properties. We list two sample questions.
Besides the intrinsic interest of questions like these, we have in mind possible application to postquantum cryptology. Concretely specified com- putational problems which are difficult to solve for almost all instances (and with certain other properties too) are in demand as primitives for public key cryptosystems, but they seem hard to come by.