Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer (Q1065546)

Lower bounds on the product TS (time \(\cdot space)\) are obtained for any general sequential model of computation with random-access input (e.g. logarithmic cost RAM) for the following two problems. For computing the discrete Fourier transform with N entries over finite prime fields TS is not \(o(N^ 2)\). For computing \(M\times M\) matrix multiplication \(TS\geq \Omega (M^ 3)\). Previously the same bounds were ascertained for straight-line programs. As an important technical tool a notion of mixing function is introduced.