In his talk on September 10, 2020, Yuri Gurevich discussed some algorithms that run in linear time (in the “length” of an input). We are going to take it up a notch and discuss what can be done in sublinear time; in particular, without reading the whole input but only a small part thereof. One well-known example is deciding divisibility of a decimal integer by 2, 5, or 10: this is done by reading just the last digit. We will discuss some less obvious examples from (semi)group theory.
This video is part of the New York Group Theory Cooperative‘s group theory seminar series.
