|
Hi everyone,
We will have a theory seminar this week on Friday, Nov 1 in the usual 2-3pm time at CS 3310. The speaker in Chuanqi Zhang (a previous UW-Madison student!)
Title: Faster isomorphism testing of p-groups of Frattini class-2
Abstract: The finite group isomorphism problem asks to decide whether two finite groups of order N are isomorphic. Improving the classical $N^{O(\log N)}$-time algorithm for group isomorphism is a long-standing open problem. It is generally regarded that p-groups
of class 2 and exponent p form a bottleneck case for group isomorphism in general. The recent breakthrough by Sun (STOC '23) presents an $N^{O((\log N)^{5/6})}$-time algorithm for this group class. Our work sharpens the key technical ingredients in Sun's algorithm
and further improves Sun's result by presenting an $N^{\tilde O((\log N)^{1/2})}$-time algorithm for the more general p-groups of Frattini class-2.
In this talk, I will first provide an overview of the problem background and motivation, particularly with applications in cryptography. Due to connections between groups and tensors, our main algorithm is actually about testing whether two tensors are isomorphic.
I will then present our main algorithm for the isomorphism testing between two 3-tensors. No group theory background is required for this talk.
This is joint work with GÃbor Ivanyos, Euan Mendoza, Youming Qiao and Xiaorui Sun, and has been accepted to FOCS 2024.
Bio: Chuanqi Zhang is a Ph.D. candidate at the Centre for Quantum Software and Information, University of Technology Sydney. He is interested in algebraic isomorphism algorithms, multilinear algebra with implications for quantum information,
tensor decomposition with applications in quantum machine learning, and non-commutative cryptography.
|
![[Computer Systems Lab]](http://www.cs.wisc.edu/pics/csl_logo.gif){kind=logo}