The membership problem in finite groups (given by a list of generators) has attracted considerable attention over the past decades in the theory of computing as well as in computational group theory. It was the motivation behind one of the orginal sources of the concept of interactive proofs; and most recently it was studied in connection with quantum complexity classes (Aaronson and Kuperberg, Theory of Computing 2007).

Arguably, the most important representation of finite groups is by matrices over finite fields. I will discuss the membership problem in this model in the light of recent definitive results.

The analogous problem for permutation groups has been known since 1980 to be solvable in polynomial time. In contrast, for matrix groups, even the one-by-one case seems to require factoring integers and discrete logarithms; so we cannot hope to avoid these obstacles in the general case.

A quarter century of increasingly intensive study by the theoretical computer science and computational group theory communities has clarified a lot of advanced questions, especially relating to the normal structure and composition factors of such a group, but only recently have these efforts added up to an answer to the basic question: at least in odd characteristic, we can now claim that group membership can be decided in randomized polynomial time, using oracles for factoring and discrete log (and therefore it is also solvable in quantum polynomial time).

Previously similar results were known for solvable matrix groups only (Luks, FOCS 1992).

As a by-product we obtain a natural problem in BPP not known to be in RP or coRP.

The overall procedure combines new elementary algorithms with a large body of previous work, algorithmic as well as group theoretic, much of it in the black-box-group context introduced in (B-Szemeredi, FOCS 1984) that has gained popularity in the computational group theory community over the past decade. Some of the ingredients depend on detailed knowledge of the classification of finite simple groups. However, no knowledge of group theory beyond an undergraduate introduction to abstract algebra will be required for this talk.

The talk is based on joint work with Bob Beals and Akos Seress (STOC'09).