DIMACS Center, CoRE Building, Rutgers University

**Organizers:****Robert Gilman**, Stevens, Robert.Gilman at stevens.edu**Bakhodyr Khoussainov**, The University of Auckland (New Zealand), bmk at cs.auckland.ac.nz**Alexei Miasnikov**, Stevens, amiasnik at stevens.edu

**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.

- Is there an automatic group with unsolvable conjugacy problem? This open problem of long standing from the theory of automatic groups might be resolved by a counterexample, but the available methods do not seem sufficiently delicate.
- How difficult are the word problems of finitely generated groups? It is a trivial observation that the word problem restricted to a finite set of words is always solvable, and it is not hard to see that the restriction to certain infinite sets must also be solvable. But are there groups such that the restriction of the word problem to other small subsets, say all sets of density greater than 1=n for fixed n, is unsolvable? The usual constructions of groups with unsolvable word problem do not answer this question. Perhaps the theory of immune sets is relevant here.

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.

Next: Call for Participation

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on July 12, 2010.