The Polynomial Transform

Abstract

We explore a new form of DFT, which we call the Polynomial Transform. It functions over finite fields, and a size $n$ transform takes $O(n)$ operations. In the multitape Turing machine model, it allows us to multiply two $n$ bit numbers in time $n(k^{{\log }^{\ast }n}+\log p)$, where $k$ is a constant and ${\log }^{\ast }n$ is the iterated logarithm. One important consequence is that the Network Coding Conjecture is false.

6 pages, 3 figures, 1 algorithm figure

References in corpus (1)

• Nearly Optimal Sparse Fourier Transform