SEMINAR: Mathematics & Statistics Colloquium: Solving equations in free groups.

Colloquium time date and location: 4pm, Thursday 21st May, Blakers Lecture Theatre.

Speaker: Dr. Murray Elder, University of Newcastle

Title. Solving equations in free groups.

Abstract. An equation in a free group is an expression U=V where U,V are words over elements of the group and variables X,Y,Z, etc. A solution is an assignment of group elements to the variables which make the equation true.

In the 1970s, Makanin constructed a (really complicated) algorithm which decides if an equation has a solution or not. Later, Razborov extended Makanin's result to find all solutions. The complexity of these algorithms was subsequently shown to be pretty bad.

In this talk I will present a new approach, describing a finite graph that encodes all solutions in reduced words, which has exponential size and can be constructed in nondeterministic quasilinear space (in the length of the equation). I will try to motivate and explain the problem, how it relates to some questions in logic, and give some of the ingredients of the proof.