Re: [theory students] Theory seminar today! At 2-3pm in CS3310

[Sandeep Silwal <silwal@xxxxxxxxxxx>]

Happening soon!

> On Nov 1, 2024, at 9:26âAM, Sandeep Silwal <silwal@xxxxxxxxxxx> wrote:
> 
> ïHi everyone,
> 
> We will have a theory seminar today 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.
> 
> Hope to see many folks there!
> 
> Sandeep
> 
> ------------------------------------------------------------------------------
> This is a message sent to the mailing list for the Theory of Computing Seminar
> at the Computer Sciences Department of the University of Wisconsin in Madison.
> For more information, see: http://www.cs.wisc.edu/areas/theory/Seminar.