<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div dir="ltr"><meta http-equiv="content-type" content="text/html; charset=utf-8"><div dir="ltr" style="-webkit-text-size-adjust: auto;">Departments of Mathematics & Computer Science<br>Combinatorics & Theory Seminar<br><br>Tuesday, November 15, 3:30pm<br>Location Kent 107<b> </b></div><div dir="ltr" style="-webkit-text-size-adjust: auto;"><br></div><div dir="ltr" style="-webkit-text-size-adjust: auto;">SPEAKER: Vladimir Shpilrain (City College of New York)</div><div dir="ltr" style="-webkit-text-size-adjust: auto;"><br>TITLE: Complexity of algorithms in group theory</div><div dir="ltr" style="-webkit-text-size-adjust: auto;"><br>ABSTRACT:<font face="Arial, sans-serif"><span style="white-space: pre-wrap;"> </span></font> The worst-case complexity of group-theoretic algorithms has been studied for a long time. Generic-case complexity, or complexity on random inputs, was introduced and studied relatively recently. In this talk, we address the average-case time complexity of several algorithms in group theory and show that in many cases it is linear and in some cases even constant (with respect to the length of an input). Along the way, we improve several bounds for the worst-case complexity of the word problem in groups of matrices, in particular in nilpotent groups. </div><div dir="ltr" style="-webkit-text-size-adjust: auto;"><br></div><div dir="ltr" style="-webkit-text-size-adjust: auto;"> Most of this talk is based on joint work with Alexander Olshanskii.</div><div dir="ltr"></div></div></body></html>