SEMINAR: Groups and Combinatorics Seminar, Straight-line programs with memory and applications to computational group theory

Abstract:

Straight-line programs offer a method for encoding group computations in a "black box" sense, namely without using specifics of the group's representation or how the group operations are performed. We advocate that straight-line programs designed for group computations should be accompanied by comprehensive complexity analyses that take into account not only the number of group operations needed, but also memory requirements arising during evaluation. We introduce an approach for formalising this idea and discuss a fundamental example for which our methods can drastically improve upon existing implementations. This is joint work (in progress!) with Alice Niemeyer and Cheryl Praeger.