BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1338
DTSTAMP:20230927T111049Z
SUMMARY:A Polynomial time Algorithm for the Minimum Generating set Problem
for Groups
DESCRIPTION:Speaker: Dhara Thakkar (IIT Gandhinagar)\n\nAbstract: \nFor a f
inite group G of order n\, a generating set of minimum size is called a mi
nimum generating set of G. A Cayley table for G is a representation of a g
roup to an algorithm. It stores the product of the ith and jth element for
each i\,j ∈ {1\,2\,..\,n}.\nGiven a group G of order n\, by its Cayley
table\, output the size of a minimum generating set problem is known as th
e minimum generating set (MIN-GEN) problem. The MIN-GEN problem admits a t
rivial 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.\nFinite
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 o
btain a quasi-polynomial (in m) time algorithm that outputs the size of a
minimum generating set when G is a primitive permutation group.\nThis talk
is based on the joint work with Bireswar Das\, and Andrea Lucchini.\n
URL:https://www.tcs.tifr.res.in/web/events/1338
DTSTART;TZID=Asia/Kolkata:20231003T160000
DTEND;TZID=Asia/Kolkata:20231003T173000
LOCATION:via Zoom in A201
END:VEVENT
END:VCALENDAR