Peter Mayr (CAUL/FCUL, Portugal)
05/05/2011 Quinta-feira, 5 de Maio de 2011, 14h30m, Sala B1-01
Institute for Interdisciplinary Research
All functions on p-groups are basically linear
I will explain the statement in the title and give a proof using some basic facts from representation theory. Then I will apply it to obtain an efficient algorithm for deciding the Subpower Membership Problem for every finite p-group with additional operations (e.g., rings, K-algebras, Lie algebras, ...).
Here the Subpower Membership Problem for a fixed algebra A is the following:
Input: tuples a_1, ..., a_k and b in A^n
Problem: Is b in the subalgebra of A^n that is generated by a_1, ..., a_k?