Time-Space Tradeoffs for Branching Programs Contrasted With Those for Straight-Line Programs

This paper establishes time-space tradeoffs for some algebraic problems in the branching program model, including convolution of vectors, matrix multiplication, matrix inversion, computing the product of three matrices and computing $PAQ$ where $P$ and $Q$ are permutation matrices. While some of the results agree well with known results for straight- line programs, one of them (for matrix multiplication) surprisingly is stronger, and one (for computing $PAQ$) is necessarily weaker. Some of the tradeoffs are proved for expected time and space, where all inputs are equally likely.