[ont.events] U of Toronto computer science seminar, July 13

clarke@csri.toronto.edu (Jim Clarke) (07/08/88)

        THEORY SEMINAR, Wednesday, July 13, 1:30 - 3:30 pm, SF1105
         (SF = Sandford Fleming Building, 10 King's College Road)

                               Avi Wigderson
                             Hebrew University

               ``Completeness Theorems for Non-Cryptographic
                  Fault-Tolerant Distributed Computation"

Every function of n inputs can be efficiently computed by a complete net-
work of n processors in such a way that:

1.   If no faults occur, no set of size t < n/2 of players gets any addi-
     tional information (other than the function value),

2.   Even if Byzantine faults are allowed, no set of size t < n/3 can
     either disrupt the computation or get additional information.

Furthermore, the above bounds on t are tight!
-- 
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
              (416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu     CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke