205 citations · 385 across the 10 of their papers we have counts for
13 papers
Pseudorandomness of the Sticky Random Walk
Emile Anand, Chris Umans
We extend the pseudorandomness of random walks on expander graphs using the sticky random walk. Building on prior works, it was recently shown that expander random walks can fool a…
Matrix multiplication via matrix groups
Jonah Blasiak, Henry Cohn, Joshua A. Grochow +2
In 2003, Cohn and Umans proposed a group-theoretic approach to bounding the exponent of matrix multiplication. Previous work within this approach ruled out certain families of grou…
Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020
Shuchi Chawla, Jelani Nelson, Chris Umans +1
Theoretical computer science (TCS) is a subdiscipline of computer science that studies the mathematical foundations of computational and algorithmic processes and interactions. Wor…
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…
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…
A new algorithm for fast generalized DFTs
Chloe Ching-Yun Hsu, Chris Umans
We give an new arithmetic algorithm to compute the generalized Discrete Fourier Transform (DFT) over finite groups . The new algorithm uses operations to c…