[Colloquium] CS Theory Seminar - Vladimir Shpilrain, Tuesday, November 15, 2022

[Jose J Fragoso]

UNIVERSITY OF CHICAGO

COMPUTER SCIENCE DEPARTMENT

PRESENTS



Vladimir Shpilrain
City College of New York


 [A picture containing person, outdoor, building, crowd  Description automatically generated]

Tuesday, November 15, 2022 at 3:30pm
Kent Chemical Laboratory, Room 107


Title:  “Complexity of Algorithms in Group Theory”

Abstract:  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.


Bio: 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 Title: algorithms and information security.



Host: Alexander Razborov




--
Jose J Fragoso
Project Assistant IV
Computer Science Department
5730 S. Ellis – Room 200C
Chicago, IL. 60637
jfragoso at uchicago.edu
(773) 702-6614
(773) 702-8487 FAX

[signature_1572818061]



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20221103/ae033985/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.png
Type: image/png
Size: 459568 bytes
Desc: image003.png
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20221103/ae033985/attachment-0001.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 91056 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20221103/ae033985/attachment-0001.jpg>