[Theory] UC Theory Seminar: a reminder
Alexander Razborov
razborov at uchicago.edu
Mon Nov 14 11:26:10 CST 2022
Departments of Mathematics & Computer Science
Combinatorics & Theory Seminar
Tuesday, November 15, 3:30pm
Location Kent 107
SPEAKER: Vladimir Shpilrain (City College of New York)
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 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.
Most of this talk is based on joint work with Alexander Olshanskii.
More information about the Theory
mailing list