We are interested in highly efficient algorithms for word problems of groups: the algorithm should read the input word once from left to right symbol by symbol (such algorithms are known as streaming algorithms), spending ideally only constant time for each input letter. Moreover, the space used by the algorithm should be small, e.g. O(log n) if n is the length of the input word. To achieve these goals we need randomization: the algorithm is allowed to make random guesses and at the end it gives a correct answer (is the input word trivial in the underlying group?) with high probability. We show that for a large class of groups such algorithms exist, where in particular the space complexity is bounded by O(log n). These groups are obtained by starting with finitely generated linear groups and closing up under the following operations: finite extensions, graph products, and wreath products where the left factor is f.g. abelian. We also contrast this result with lower bounds. For instance, for Thompson’s group F every randomized streaming algorithm for the word problem for F has space complexity Ω(n) (n is again the length of the input word).
This video is part of the New York Group Theory Cooperative‘s group theory seminar series.
