🚀 go-pugleaf

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.