[Colloquium] [CS] THEORY SEMINAR TALK TODAY: YouMing (Jimmy) Qiao

[Donna Brooms]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO - THEORY SEMINAR

Date: Tuesday, February 22, 2011
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

_______________________________________

Speaker:  YouMing (JImmy) Qiao

From:       Tsinghua University

Web page: http://itcs.tsinghua.edu.cn/youmingqiao/

Title:         On isomorphism testing of groups with normal Hall subgroups

Abstract:      Group isomorphism problem, when groups are represented as multiplication tables, asks for an efficient algorithm to test if two given groups are isomorphic or not. Though an n^{logn + O(1)} algorithm has been known for decades, whether a polynomial algorithm exists is still elusive. To make progress towards the general case, people have been considering restricted group classes. Abelian groups has been understood well while making further progress seems difficult. In 2008, Le Gall presented efficient isomorphism testing for groups in the form of semidirect product of abelian group by cyclic group, where two components are coprime. 

With Jayalal Sarma and Bangsheng Tang, we extend Le Gall's work to a much more general framework, to test isomorphism of groups with at least one normal Hall subgroup (a normal subgroup whose order is coprime with its index). The most notable feature of this framework is to give a connection between group isomorphism problem and group representation theory. In fact, it turns out that the following computational problem in group representation theory lies in the core of testing isomorphism of such groups:

Given two representations ρ and τ of a group H over Z^d_p, p a prime, determine if there exists an automorphism ϕ : H → H, such that the induced representation ρϕ = ρ ◦ ϕ and τ are equivalent, in time poly(|H|, p^d).

We solve the above problem when H is elementary abelian (that is, a vector space over finite field), by reducing to code equivalence problem, which asks if two linear codes are the same up to permutation of coordinates. Utilizing a singly exponential algorithm by Babai, we can efficiently test isomorphism of groups in the form of semidirect product of abelian group by elementary abelian group, whose orders are coprime. As far as we know, this is the first group class with n^{Omega(log n)} non-isomorphic groups in it, whose isomorphism can be tested efficiently. 


Host:		Prof. Alexander Razborov

Refreshments will be served prior to the talk at 2:30 in Ryerson 255

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20110222/ecee4f8c/attachment.htm