<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:0 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:10.0pt;
font-family:"Calibri",sans-serif;}
p.p1, li.p1, div.p1
{mso-style-name:p1;
margin:0in;
font-size:8.5pt;
font-family:Helvetica;
color:#FF9400;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="#0563C1" vlink="#954F72" style="word-wrap:break-word">
<div class="WordSection1">
<p class="p1"><i><span style="font-size:12.0pt;color:windowtext"> </span></i><o:p></o:p></p>
<p class="p1"><i><span style="font-size:12.0pt;color:#C00000">UNIVERSITY OF CHICAGO</span></i><o:p></o:p></p>
<p class="p1"><i><span style="font-size:12.0pt;color:#C00000">COMPUTER SCIENCE DEPARTMENT</span></i><o:p></o:p></p>
<p class="p1"><i><span style="font-size:12.0pt;color:#C00000">PRESENTS</span></i><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt">
</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica">Vladimir Shpilrain</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica">City College of New York</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica"> </span></b><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica"> </span></b><img width="269" height="264" style="width:2.802in;height:2.75in" id="Picture_x0020_4" src="cid:image001.jpg@01D8E943.A0586D60" alt="A picture containing person, outdoor, building, crowd
Description automatically generated"><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt">Tuesday, November 15, 2022 at 3:30pm</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;background:yellow;mso-highlight:yellow">Kent Chemical Laboratory, Room 107</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal" align="center" style="text-align:center;background:white"><b><span style="font-size:14.0pt;font-family:"Arial",sans-serif;color:black"> </span></b><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom:8.0pt;mso-line-height-alt:11.75pt"><b><i><span style="font-size:12.0pt">Title:</span></i></b><span style="font-size:12.0pt">
</span><b><span style="font-size:14.0pt;font-family:"Arial",sans-serif;color:black">“</span></b><b><span style="font-size:14.0pt;font-family:"Arial",sans-serif">Complexity of Algorithms in Group Theory<span style="color:black">”</span></span></b><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom:8.0pt;line-height:11.75pt"><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black">Abstract:</span></i></b><i><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black">
</span></i><span style="font-size:12.0pt;font-family:"Arial",sans-serif;color:black">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 the 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. Most of this talk is based on joint work with Alexander Olshanskii.</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom:8.0pt;line-height:11.75pt"> <o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Bio:</span></i></b><b><span style="font-size:12.0pt;font-family:"Arial",sans-serif">
</span></b><span style="font-size:12.0pt;font-family:"Arial",sans-serif;color:black">Vladimir Shpilrain is a Professor of Mathematics at the City College of New York and CUNY Graduate Center. He is the (co-)author of 120+ papers and 4 monographs. His main research
interests are complexity of </span><b><i><span style="font-size:12.0pt">Title:</span></i></b><span style="font-size:12.0pt">
</span><span style="font-size:12.0pt;font-family:"Arial",sans-serif;color:black">algorithms and information security. </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"> </span><o:p></o:p></p>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica">Host: Alexander Razborov</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica"> </span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt">-- </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Jose J Fragoso</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Project Assistant IV</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Computer Science Department</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">5730 S. Ellis – Room 200C</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Chicago, IL. 60637</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">jfragoso@uchicago.edu</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">(773) 702-6614</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">(773) 702-8487 FAX</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"><img width="92" height="92" style="width:.9583in;height:.9583in" id="Picture_x0020_1" src="cid:image003.png@01D83D68.0E6B3630" alt="signature_1572818061"></span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"> </span><o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
</div>
</body>
</html>