BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Colva Roney-Dougal (The University of St Andrews) DTSTART:20201008T150000Z DTEND:20201008T160000Z DTSTAMP:20260423T053045Z UID:GOThIC/1 DESCRIPTION:Title: F inite simple groups and complexity class NP\nby Colva Roney-Dougal (Th e University of St Andrews) as part of GOThIC - Ischia Online Group Theory Conference\n\n\nAbstract\nThis talk will describe connections between str uctural results about the finite simple groups and the complexity of compu tational algorithms for permutation groups.\n\nThe first part of the talk will discuss the base size of a permutation group\, an invariant which det ermines the complexity of many permutation group algorithms. We will prese nt a new\, optimal\, bound on the base size of the primitive groups that a re not large base. After this\, we will discuss some group-theoretic quest ions for which there is no known polynomial time solution. In particular\, we shall present a new approach to computing the normaliser of a primitiv e group $G$ in an arbitrary subgroup $H$ of $S_{n}$. Our method runs in qu asipolynomial time $O(2^{log^3 n})$\, whereas the previous best known algo rithm required time $O(2^n)$.\n\nThis is partly joint work with Mariapia M oscatiello (Padova)\, and partly with Sergio Siccha (Siegen).\n LOCATION:https://researchseminars.org/talk/GOThIC/1/ END:VEVENT END:VCALENDAR