This paper introduces communicating branching programs and develops a general technique for demonstrating communication-space tradeoffs for pairs of communicating branching programs. This technique is then used to prove communication-space tradeoffs for any pair of communicating branching programs that hashes according to a universal family of hash functions. Other tradeoffs follow from this result. As an example, any pair of communicating Boolean branching programs that computes matrix-vector products over ${\text{GF}}(2)$ requires communication-space product $\Omega (n^2 )$, provided the space used is $o({n / {\log n}})$. These are the first examples of communication-space tradeoffs on a completely general model of communicating processes.

Communicating branching programs are introduced, and a general technique for demonstrating communication-space tradeoffs for pairs of communicating branching programs is developed. The technique is used to prove communication-space tradeoffs for any pair of communicating branching programs that hashes according to a universal family of hash functions. Other tradeoffs follow from this result. For example any pair of communicating Boolean branching programs that computes matrix-vector products over GF(2) requires communication-space product Omega (n/sup 2/). These are the first examples of communication-space tradeoffs on a completely general model of communicating processes.>

For polynomially bounded weights and polylogarithmic precision, analog neural networks of polynomial size and depth 3 are strictly more powerful than those of polynomial size and depth 2.