| Speaker: Alex Lubotzky Affiliation: Hebrew University Time: 15:00 Tuesday, 3 March, 2020 Location: 303-G14 |
| Generating a ( pseudo) random element in a finite group, given by a set of generators, is a basic challenge in computational group theory. In the 1990's a new method, the so called Product Replacement Algorithm (PRA), was designed by Leedham-Green and Soicher and checked and analysed carefully in [CLMNO]. While the performance of the PRA was outstanding, it was not easy to explain it theoretically. In 2000, an explanation was suggested in [LP] based on the conjecture that "Aut(Fn) has Kazhdan property (T) " and the theory of expanders. This conjecture was proved recently by M. Kaluba, D. Kielak and P. Nowak and hence the mystery is now fully explained. We will describe these developments and explain the various connections. [CLMNO] F. Celler, C.R. Leedham-Green, S. Murray, A. Niemeyer, and E.A. O'Brien, Generating random elements of a finite group, Comm. Alg. 23 (1995), 4931--4948. [LP] A. Lubotzky and I. Pak, The product replacement algorithm and Kazhdan's property (T), J. Amer. Math. Soc. 14 (2001), no. 2, 347--363 |