For a finite group G of order n, a generating set of minimum size is called a minimum generating set of G. A Cayley table for G is a representation of a group to an algorithm. It stores the product of the ith and jth element for each i,j ∈ {1,2,..,n}.
Given a group G of order n, by its Cayley table, output the size of a minimum generating set problem is known as the minimum generating set (MIN-GEN) problem. The MIN-GEN problem admits a trivial algorithm that runs in time n^{\log n+O(1)}. In this talk, I will present a polynomial time algorithm that solves the MIN-GEN problem. Our algorithm also finds one minimum generating set for a given group.
Finite groups can also be represented by their generating set as input. Let G \leq S_m be a primitive permutation group given by its generating set. We obtain a quasi-polynomial (in m) time algorithm that outputs the size of a minimum generating set when G is a primitive permutation group.
This talk is based on the joint work with Bireswar Das, and Andrea Lucchini.
