Speaker: Richard Chang
<br>
<br>
Title: Complexity of Group Membership and Iterated
Product Problems on Groups Given as Multiplication Tables
<br>
<br>
This talk will cover much of the work of Barrington, Kadau, Lange, and
McKenzie in "On the Complexity of Some Problems on Groups Input as
Multiplication Tables."  Specifically, I will discuss the complexity of
testing properties of groups (abelianess, solvability, etc).  Introduce the
complexity class FO(log log n) of problems solvable by uniform poly-size
circuit families of unbounded fan-in and depth O(log log n).  I will show no problem in FOLL can be hard for L or for any other class containing PARITY.  I will discuss the complexity of the CGM problem defined as given a group G as a
multiplication table, a subset X of G, and a target element t, determining
whether or not the subgroup generated by X contains t for various classes of
groups (cylic, abelian, nilpotent).  Additionally, I will discuss the
complexity of the ITERATED PRODUCT problem for various classes of groups
given as Cayley tables.