Branching programs

From: Srikanth (srinivasan.srikanth_at_gmail.com)
Date: 12/29/04 

Date: 29 Dec 2004 07:26:41 -0800

Hi all,
I am currently doing some research on time-space tradeoffs as
part of an undergraduate project. I want to do a survey on the general
field of time-space tradeoffs and specifically, results relating to
branching programs. I have found the following papers:

- "Time-space tradeoffs for sorting on a general sequential model of
computation" by Allan Borodin and Stephen Cook, STOC 1982.
- "A general sequential time space tradeoff for finding unique
elements" by Paul Beame, SIAM journal of computing 1991.

and two other recent results by Miklos Ajtai.

What are the other important results I should get familiar with? Is
there a survey on branching programs in particular?

Thanks,
Srikanth.