Zobrazeno 1 - 10
of 42
pro vyhledávání: '"Umans, Chris"'
The Cohn-Umans (FOCS '03) group-theoretic framework for matrix multiplication produces fast matrix multiplication algorithms from three subsets of a finite group $G$ satisfying a simple combinatorial condition (the Triple Product Property). The compl
Externí odkaz:
http://arxiv.org/abs/2410.14905
Autor:
Anand, Emile, Umans, Chris
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 all symmetric functions in total variation distance (TVD) upto an $O(\l
Externí odkaz:
http://arxiv.org/abs/2307.11104
Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate
Externí odkaz:
http://arxiv.org/abs/2205.00342
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 groups as a route to obtaining $\omega = 2$, while other families of group
Externí odkaz:
http://arxiv.org/abs/2204.03826
Publikováno v:
Journal of the ACM; Jun2024, Vol. 71 Issue 3, p1-32, 32p
Theoretical computer science (TCS) is a subdiscipline of computer science that studies the mathematical foundations of computational and algorithmic processes and interactions. Work in this field is often recognized by its emphasis on mathematical te
Externí odkaz:
http://arxiv.org/abs/2107.02846
Autor:
Umans, Chris
For any finite group $G$, we give an arithmetic algorithm to compute generalized Discrete Fourier Transforms (DFTs) with respect to $G$, using $O(|G|^{\omega/2 + \epsilon})$ operations, for any $\epsilon > 0$. Here, $\omega$ is the exponent of matrix
Externí odkaz:
http://arxiv.org/abs/1901.02536
The Cohn-Umans group-theoretic approach to matrix multiplication suggests embedding matrix multiplication into group algebra multiplication, and bounding $\omega$ in terms of the representation theory of the host group. This framework is general enou
Externí odkaz:
http://arxiv.org/abs/1712.02302
Autor:
Hsu, Chloe Ching-Yun, Umans, Chris
We give an new arithmetic algorithm to compute the generalized Discrete Fourier Transform (DFT) over finite groups $G$. The new algorithm uses $O(|G|^{\omega/2 + o(1)})$ operations to compute the generalized DFT over finite groups of Lie type, includ
Externí odkaz:
http://arxiv.org/abs/1707.00349
Autor:
Hoza, William M., Umans, Chris
Assume that for every derandomization result for logspace algorithms, there is a pseudorandom generator strong enough to nearly recover the derandomization by iterating over all seeds and taking a majority vote. We prove under a precise version of th
Externí odkaz:
http://arxiv.org/abs/1610.01199