Multiparty protocols and logspace-hard pseudorandom sequences

ABSTRACT

Let ƒ(x1, ···· xk) be a Boolean function that k parties wish to collaboratively evaluate. The i'th 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 &OHgr;(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=&THgr;(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 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).

REFERENCES

• AKLLR: R. Aleliunas, R.M. Karp, R.j. Lipton, L. Lovasz and C. Rackoff, "Random walks, universal traversing sequences and the complexity of maze problems", FOCS '79.
• AM: N. AIon and W. Maass, "Meanders, Ramsey theory and lower bounds for branching programs", FOCS '86.
• AUY: Alfred V. Aho , Jeffrey D. Ullman , Mihalis Yannakakis, On notions of information transfer in VLSI circuits, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.133-139, December 1983 [doi>10.1145/800061.808742]
• AW: M. Ajtai and A. Wigderson, "Deterministic simulation of Probabilistic constant depth circuits'', 26th FOCS, pp. 11-19, 1985.
• BCDRT: A. Borodin, S.A. Cook, P.W. Dymond, W.L. Ruzzo and M. Tompa, "Two applications of inductive counting for complementation problems'', manuscript, 1988.
• BFS: L. Babai, P. Frankl and J. Simon, "Complexity classes in communication complexity theory", FOCS '86.
• BlM: M. Blum and S. Micali, "How to generate cryptographically strong sequences of pseudo random bits", 23rd FOCS, pp. 112-I 17, 1982.
• CFL: Chandra, Furst and Lipton, "Multiparty protocols'', FOCS '83.
• CG: B. Chor and O. Goldreich, "Unbiased bits from weak sources of randomness", FOCS '85.
• DG: P. Duris and Z. Galil, "A time-space tradeoff for language recognition", Math. Systems theory 17 3-12, 1984.
• GuS: Yuri Gurevich , Saharon Shelah, Nondeterministic linear tasks may require substantially nonlinear deterministic time in the case of sublinear work space, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.281-289, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62239]
• ILL: R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
• Is: Sorin Istrail, Polynomial universal traversing sequences for cycles are constructible, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.491-503, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62260]
• Ka: Mauricio Karchmer, Two time-space tradeoffs for element distinctness, Theoretical Computer Science, v.47 n.3, p.237-246, Nov., 1986
• KLNS: J.D. Kahn, N. Linial, N. Nisan and M.E. Saks, "On the cover time of random walks in graphs", Journal of Theoretical Probability, Vol. 2, No. 1, 1989.
• Kn: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• KPS: H. Karlof, R. Paturi and J. Simon, "Universal sequences of length n~(t~~ for cliques", manuscript, 1987.
• Ne: E.I. Necipomk, "A boolean function", Soviet Mathematics Doklady 7:4, 999-1000, 1966.
• Ni: N. Nisan, "l-way vs. 2-way access to randomness in Logspace", manuscript, 1989.
• NW: N. Nisan and A. Wigderson, "Hardness vs. Randomness", FOCS '88.
• RT: I.H. Reif and J.D. Tygar, "Towards a theory of parallel randomized computation", TR-07- 84, Aiken computation lab., Harvard university, 1984.
• Va: U V Vazirani, Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.366-378, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22186]
• Ya1: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]
• Y2: A.C. Yao, "Theory and applications of trapdoor functions", 23rd FOCS, pp. 80-91, 1982.
• Y3: A.C. Yao, "Lower bounds by probabilistic arguments", STOC '83.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Algorithms, Theory