BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Uri Andrews (University of Wisconsin) DTSTART:20250417T180000Z DTEND:20250417T190000Z DTSTAMP:20260423T035934Z UID:OLS/176 DESCRIPTION:Title: Gr oup word problems revisited\nby Uri Andrews (University of Wisconsin) as part of Online logic seminar\n\n\nAbstract\nPre-dating computability th eory\, Max Dehn proposed to find algorithms to answer\, for a given group presentation\, word problem of the group: whether two given words in the generators are equal in the group. Novikov and Boone showed in the 50s tha t some simply presented groups can have undecidable word problem. In fact\ , every r.e. degree contains the word problem of a finitely presented grou p. From the perspective of the Turing degrees\, this gives a complete answ er to the question of the complexity of word problems of groups. The answe r is: Every possible complexity.\n\nI will present a different perspective on studying word problem complexity: We study the complexity of word prob lems as equivalence relations under computable reducibility. That is\, we say that an equivalence relation R reduces to an equivalence relation E if there is a computable function f so that xRy if and only if f(x) E f(y). In this structure\, we find a more subtle picture\, beginning with the fac t that not every degree is the degree of a the word problem of a group. So me surprising phenomena appear. Work joint with Turbo Ho and Luca San Maur o.\n LOCATION:https://researchseminars.org/talk/OLS/176/ END:VEVENT END:VCALENDAR