Coded Fourier Transform
  We consider the problem of computing the Fourier transform of
high-dimensional vectors, distributedly over a cluster of machines consisting
of a master node and multiple worker nodes, where the worker nodes can only
store and process a fraction of the inputs. We show that by exploiting the
algebraic structure of the Fourier transform operation and leveraging concepts
from coding theory, one can efficiently deal with the straggler effects. In
particular, we propose a computation strategy, named as coded FFT, which
achieves the optimal recovery threshold, defined as the minimum number of
workers that the master node needs to wait for in order to compute the output.
This is the first code that achieves the optimum robustness in terms of
tolerating stragglers or failures for computing Fourier transforms.
Furthermore, the reconstruction process for coded FFT can be mapped to MDS
decoding, which can be solved efficiently. Moreover, we extend coded FFT to
settings including computing general $n$-dimensional Fourier transforms, and
provide the optimal computing strategy for those settings.
