Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs

摘要

Let f(x1, …, xk) be a Boolean function that k parties wish to collaboratively evaluate, where each xi is a bit-string of length n. The ith party knows each input argument except xi; 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) polynomial time computable functions. Our bounds hold even if the parties only wish to have a 1 % advantage at guessing the value of f on random inputs. The lower bound proofs are based on discrepancy upper bounds for specific functions over “cylinder intersection” sets. These results may be of independent interest. We give several applications of the lower bounds. The 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 √log n) that no Logspace Turing machine will be able to distinguish from truly random sequences. As a corollary we give an explicit construction of a universal traversal sequence of length exp(exp(c√log n)) for arbitrary undirected graphs on n vertices. We then apply the multiparty protocol lower bounds to derive several new time-space trade-offs. We give a tight time-space trade-off of the form TS =Θ(n2), 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 trade-off 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). Using universal hashing, Nisan has recently constructed considerably improved random generators for Logspace, with the implication of shorter explicit universal traversal sequences. The time-space and related trade-off results mentioned above are not affected by this development.