sjb@ai.toronto.edu (Stephen Bellantoni) (08/24/88)
The seminar date has changed: THEORY SEMINAR, *FRIDAY, AUGUST 26* at 11 a.m., SF1101 -- Noam Nisan: "Multiparty Protocols and Logspace-Hard Pseudorandom Sequences" -------------------------------------------------- THEORY SEMINAR, *Friday, August 26* at 11 a.m., SF1101 Noam Nisan U. California, Berkeley "Multiparty Protocols and Logspace-Hard Pseudorandom Sequences" We construct a pseudo-random sequence generator that "stretches" a short seed of truly random bits to a long string which "looks random" to any Logspace Turing machine. Unlike the known con- structions of pseudo- random generators which require some unpro- ven "hardness" assumption, we make no unproven assumptions but rather reduce the problem to that of proving lower bounds on the complexity of the following multiparty communi- cation game: Let f(x1,x2,...,xk) be a Boolean function that k parties wish to colla- boratively evaluate. The i'th party knows each input argu- ment 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 for the number of bits that need to be ex- changed, by that completing the proof of the security of the pseudo-random gen- erator.