Multiparty protocols and logspace-hard pseudorandom sequences

Let ƒ(x₁, ···· x_k) be a Boolean function that k parties wish to collaboratively evaluate. The i'th party knows each input argument except x_i; and each party has unlimited computational power. They share a blackboard, viewed by all parties, where they can exchange messages. The objective is to minimize the number of bits written on the board.

We prove lower bounds of the form Ω(n·c^-k), for the number of bits that need to be exchanged in order to compute some (explicitly given) functions in P. Our bounds hold even if the parties only wish to have a 1% advantage at guessing the value of ƒ on random inputs. We then give several applications of our lower bounds.

Our first application is a pseudorandom generator for Logspace. We explicitly construct (in polynomial time) pseudorandom sequences of length n from a random seed of length exp(c√logn) that no Logspace Turing machine will be able to distinguish from truly random sequences. As a corollary we give an explicit construction of universal traversal sequence of length exp(exp(c√logn)) for arbitrary undirected graphs on n vertices.

We then apply the multiparty protocol lower bounds to derive several new time-space tradeoffs. We give a tight time-space tradeoff of the form TS=Θ(n²), for general, k-head Turing-Machines; the bounds hold for a function that can be computed in linear time and constant space by a k+1-head Turing Machine. We also give a new length-width tradeoff for oblivious branching programs; in particular our bound implies new lower bounds on the size of arbitrary branching programs, or on the size of Boolean formulas (over an arbitrary finite base).