BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Michael Levet (CU Boulder) DTSTART:20220419T190000Z DTEND:20220419T200000Z DTSTAMP:20260423T004136Z UID:PALS/29 DESCRIPTION:Title: We isfeiler—Leman for Group Isomorphism: Action Compatibility\nby Micha el Levet (CU Boulder) as part of PALS Panglobal Algebra and Logic Seminar\ n\n\nAbstract\nThe Weisfeiler—Leman (WL) algorithm is a key combinatoria l subroutine in Graph Isomorphism\, that (for fixed $k \\geq 2$) computes an isomorphism invariant coloring of the k-tuples of vertices. Brachter & Schweitzer (LICS 2020) recently adapted WL to the setting of groups. Using a classical Ehrenfeucht-Fra\\"iss\\'e pebble game\, we will show that Wei sfeiler—Leman serves as a polynomial-time isomorphism test for several f amilies of groups previously shown to be in $\\textsf{P}$ by multiple meth ods. These families of groups include:\n\n(1) Coprime extensions $H \\ltim es N$\, where $H$ is $O(1)$-generated and the normal Hall subgroup $N$ is Abelian (Qiao\, Sarma\, & Tang\, STACS 2011).\n\n(2) Groups without Abelia n normal subgroups (Babai\, Codenotti\, & Qiao\, ICALP 2012). \n\n \nIn bo th of these cases\, the previous strategy involved identifying key group-t heoretic structure that could then be leveraged algorithmically\, resultin g in different algorithms for each family. A common theme among these is t hat the group-theoretic structure is mostly about the action of one group on another. Our main contribution is to show that a single\, combinatorial algorithm (Weisfeiler-Leman) can identify those same group-theoretic stru ctures in polynomial time.\n\n \n\nWe also show that Weisfeiler—Leman re quires only a constant number of rounds to identify groups from each of th ese families. Combining this result with the parallel WL implementation du e to Grohe & Verbitsky (ICALP 2006)\, this improves the upper bound for is omorphism testing in each of these families from $\\textsf{P}$ to $\\texts f{TC}^0$.\n\n \n\nThis is joint work with Joshua A. Grochow.\n LOCATION:https://researchseminars.org/talk/PALS/29/ END:VEVENT END:VCALENDAR