Abstract: In her PhD thesis of sixty years ago, Julia Robinson proved that the theory of the field of rational numbers is undecidable. To do this, she showed that the ring of integers is first-order definable in the rationals. Her proof employed representations of integers by quadratic forms; the resulting formula which defines the integers in the rationals involves several alternations of quantifiers. Recently Bjorn Poonen, using quaternion algebras, found a formula which does the same job, but with only one alternation of quantifiers. We will survey these results, and indicate some connections to the work of others on Hilbert's 10th problem over various rings.

Abstract: It is now well known that the word problem for groups is undecidable; that is, it is not possible to write a computer program that takes as input a finite group presentation and a word in the generators and decides whether the given word represents the identity in the group. In 1981 Kharlampovich proved that even when we restrict our attention to finite presentations of solvable groups, the word problem remains undecidable. If we restrict the groups still further to the class of finitely presented metabelian groups, the word problem is decidable, as are a host of other problems such as conjugacy and generalized conjugacy, but the decidability of some other problems in this context remains open, such as subgroup conjugacy and computing intersections of subgroups. In this talk I will discuss recent progress on these problems for free metabelian groups. This is joint work with Gilbert Baumslag and Chuck Miller.

Abstract: This is joint work with Sy-David Friedman. The well-known Koenig's Lemma states that every finitely branching tree of countably infinite height contains an infinite path through the tree. However, the natural generalization of Koenig's Lemma to trees of uncountable height breaks down. Precisely, Aronszajn constructed a tree of height $\omega_1$ (the first uncountable cardinal) such that every level of the tree is countable, yet the tree contains no branch going all the way through it. Such a tree is called an $\omega_1$-Aronszajn tree.
When looking at larger uncountable cardinals, the picture becomes even more complicated. For any regular cardinal $\kappa\ge\aleph_2$, the non-existence of $\kappa$-Aronszajn trees requires axioms in addition to those of ZFC (the standard axioms of set theory, and much of mathematics in general). In this talk, we will investigate when $\kappa$-Aronszajn trees exist and when they do not. In particular, we find the equiconsistency strength of there being no $\kappa^{++}$-Aronszajn trees when $\kappa$ is a measurable cardinal.

Abstract: Decision problems such as the word and conjugacy problems lie at the juncture of group theory and theoretical computer science, and have become instrumental in creating new, and hopefully secure, cryptographic schemes. I will outline several key exchange protocols which depend on different decision problems. The question of which groups to use when implementing these procedures is multi-faceted. Thompson's group F was proposed as a platform for one of these key exchange protocols. I will give a brief introduction to this group, highlight my contributions to understanding its geometry and metric properties, and describe how it is used in the key exchange procedure. Then I will describe a simple proof (due to F. Matucci) showing that any encryption using this group and this procedure is not secure.

Abstract: This talk will be addressed to a general mathematical audience. The contents are a consequence of the close connection between combinatorial group theory and the topology of surfaces, where the fundamental groups are either one relator groups or free groups.
Consider the free Z-module generated by the set of directed free homotopy classes of closed curves on a orientable surface. Goldman proved that on this Z-module there exists a Lie algebra structure, obtained by combining the geometric intersection of curves with the usual loop product of curves at intersection points. Since free homotopy classes of curves on a surface are in one to one correspondence with conjugacy classes of the fundamental group, this implies for each surface the existence of a Lie algebra structure on the Z-module generated by the conjugacy classes of the surface group. We will give a definition of this Lie algebra and discuss several of its properties.
When a free homotopy class of curves is simple, i.e. has a representative with no self-intersections, one can write the fundamental group of the surface as an amalgamated free product or an HNN extension of certain subgroups. Using this fact, we will give a combinatorial description of the Goldman Lie bracket of a simple class with any other free homotopy class. We will use this description to prove that there is no cancellation and consequently the number of terms of the bracket, counted with multiplicity, is the minimal intersection number of theses two free homotopy classes.
When the surface has non-empty boundary, there is a combinatorial presentation of the entire Goldman Lie bracket. Using this presentation we find an algorithm to count the minimal number of self-intersections of a free homotopy class of curves.
There are open problems related to the characterization of which conjugacy classes contain simple closed curves. Namely, certain "commutator words" constructed using a word which has a simple representative should not be conjugate. There is also the problem of determining the centers of these Lie algebras.

Abstract: I will briefly outline some of the key points (see below) in our proof with A. Myasnikov of the Tarski conjectures about the elementary theory of a free group and outline some applications of methods and techniques. These conjectures stated that the elementary theory of non-abelian free groups of different ranks coinside and that this common theory is decidable. The first conjecture was independently proved by Sela. The key points are:
1. Development of the algebraic geometry over groups in several papers by Baumslag, Myasnikov, Remeslennikov and myself;
2. The theory of fully residually free groups (limit groups) and a simple algebraic description of them, embedding of fully residually free groups into NTQ groups;
3. Implicit function theorem for regular quadratic and NTQ systems of equations in free groups, Skolem functions;
4. Elimination process that works in groups with free Lyndon's length function (which is a development of Makanin-Razborov process for solving equations in free groups);
5. Description of the solution set of systems of equations with parameters (independent of the particular values of the parameters), different finiteness conditions;
6. Solution of algorithmic problems in f.g. fully residually free groups, infinite words and effectiveness of the JSJ decomposition of a f.g. fully residually free group;
7. Decidability of the AE-theory of a free group, termination of the decision process;
8. Reduction (non-effective) of an arbitrary formula to a boolean combination of AE-formulas, effective approach to an arbitrary sentence.