# The ICICS/CS Reading Room

## UBC CS TR-87-19 Summary

- No on-line copy of this technical report is available.

- 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
help@cs.ubc.ca.