3 papers
cs.DS2019
Fast generalized DFTs for all finite groups
Chris Umans
For any finite group , we give an arithmetic algorithm to compute generalized Discrete Fourier Transforms (DFTs) with respect to , using operations, for an…
math.GR2017
Which groups are amenable to proving exponent two for matrix multiplication?
Jonah Blasiak, Thomas Church, Henry Cohn +2
The Cohn-Umans group-theoretic approach to matrix multiplication suggests embedding matrix multiplication into group algebra multiplication, and bounding in terms of the repres…
cs.CC2016
Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields
Zeyu Guo, Anand Kumar Narayanan, Chris Umans
The fastest known algorithm for factoring univariate polynomials over finite fields is the Kedlaya-Umans (fast modular composition) implementation of the Kaltofen-Shoup algorithm.…