Date & Time:
November 15, 2022 3:30 pm – 4:30 pm
Location:
Kent 107, 1020-24 East 58th St., Chicago, IL, 60637
11/15/2022 03:30 PM 11/15/2022 04:30 PM America/Chicago Vladimir Shpilrain (CCNY) – Complexity of Algorithms in Group Theory CS Theory Seminar Kent 107, 1020-24 East 58th St., Chicago, IL, 60637

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.

 

Speakers

Vladimir Shpilrain

Professor of Mathematics, City College of New York

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

Related News & Events

Students posing at competition

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023
Haifeng Xu

New CS and DSI Faculty Haifeng Xu Brings Strategic Intelligence to NeurIPS 2022

Nov 28, 2022

UChicago CS Research Finds New Angle on Database Query Processing with Geometry

Nov 08, 2022

Asst. Prof. Aloni Cohen Receives Award For Revealing Flaws in Deidentifying Data

Sep 09, 2022

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Aug 15, 2022

New 2022-23 Faculty Add Expertise in Linguistics, Visualization, Economics, and Data Science Education

Aug 11, 2022

UChicago Co-Leads $10 Million NSF Institute on Foundations of Data Science

Aug 09, 2022

Bill Fefferman Comments on New Standards for Quantum-Proof Cryptography

Jul 07, 2022

UChicago London Colloquium Features Data Science, Quantum Research

Jul 01, 2022

Faculty Bill Fefferman and Chenhao Tan Receive Google Research Scholar Awards

Jun 21, 2022

First-Year PhD Student Co-Authors Outstanding Paper Award Winner at TQC 2022

Apr 28, 2022

Quanta Magazine Features Prof. Bill Fefferman’s Work on Quantum Algorithms

Jan 20, 2022
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube