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