4 papers
Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2
Joshua A. Grochow, Gábor Ivanyos, Youming Qiao +1
The finite group isomorphism problem asks whether two finite groups of order are isomorphic. The first algorithm, attributed to Tarjan (see Miller, STOC '78), runs in time $N^{…
Random tensor isomorphism under orthogonal and unitary actions
Jeremy Chizewer, Samuel Everett, Deven Mithal +1
We study the problem of testing whether two tensors in are isomorphic under the natural action of orthogonal groups $\text…
Canonical forms for matrix tuples in polynomial time
Youming Qiao, Xiaorui Sun
Left-right and conjugation actions on matrix tuples have received considerable attention in theoretical computer science due to their connections with polynomial identity testing,…
On linear-algebraic notions of expansion
Yinan Li, Youming Qiao, Avi Wigderson +2
A fundamental fact about bounded-degree graph expanders is that three notions of expansion -- vertex expansion, edge expansion, and spectral expansion -- are all equivalent. In thi…