Time-space tradeoffs for algebraic problems on general sequential machines

摘要

This paper establishes time-space tradeoffs for some algebraic problems in the branching program model, including convolution of vectors, integer multiplication, matrix-vector products, matrix multiplication, matrix inversion, computing the product of three matrices, and computing PAQ where P and Q are permutation matrices. The lower bounds apply to general sequential models of computation. Although the lower bounds are for a more general model, they are as large as the known bounds for straight-line programs (even improving the known straight-line bounds for matrix multiplication) except for the case of computing PAQ, for which non-oblivious algorithms can outperform oblivious ones, and integer multiplication, where our lower bound is a polylogarithmic factor below the known straight-line bound. Some of the tradeoffs are proved for expected time and space, where all inputs are equally likely.