Technical Reports

The ICICS/CS Reading Room

UBC CS TR-87-19 Summary

Time-Space Tradeoffs for Branching Programs Contrasted With Those for Straight-Line Programs, June 1987 Karl Abrahamson

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.

If you have any questions or comments regarding this page please send mail to