Abstract: The Cayley Group Membership problem (CGM) is to input a groupoid (binary algebra) G given as a multiplication table, a subset X of G, and an element t of G, and to determine whether t can be expressed as a product of elements of X. For general groupoids CGM is P-complete, and for associative algebras (semigroups) it is NL-complete. We will investigate CGM for particular classes of groups. We will also introduce the complexity class FOLL, or FO(log log n) which does not contain parity and argue its importance for various group theoretic problems. Finally, we will examine the implications of these results on the complexity of various problems in the arithmetic of small numbers.
The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.